5V Songle relay, pcb slightly hotter than room temperature
You can replace the relay with a bistable (latching) type, but they are more expensive and most are designed for low power applications (2A or less). You pulse their coil to change the position. 

The coil of the relay you have dissipates 450mW or 360mW nominally depending on sensitivity type. Often there will be other heat sources on a board of similar magnitude but that coil is a significant source, and of course it varies depending on state. The contacts and traces to the contacts are also a source of heat if the normally open or normally closed contacts are carrying current and that will vary with the relay state. 

There may be other suppliers with similar parts that take less- if you don't mind changing the pinout the  G6DN-1A DC5  from Omron is only 110mW. You can also try to play games by reducing the voltage nominally or after the relay pulls in but if you actually need to operate over a  wide temperature range you may have issues (relays are actually current operated and the resistance of the coil increases with temperature so they are less likely to pull in with low voltage-- and electrical life may be compromised). 

I doubt you'll seem much improvement from slots in the PCB but you can try. If it's a multilayer board you can try to heat sink the relay part and (of course) cut out any undesirable internal planes (but you should have done most of that anyway). 

Putting a sensor on the board, as putting it on a chip, is not usually a good way to measure anything except the board temperature or die temperature respectively. 

Hey, if you want a dumb idea for free- mount a resistor nearby and turn it on when the coil is off (LED dropping resistor or something). You could probably reduce the change in temperature rise by a factor of 4:1 over a modest temperature range. 



On a different matter, you could get a bit more coil-contact creepage distance by running the coil traces straight back and necking them in at the diode. No big deal if it meets your requirements, but it could be better at no cost.