Relays drawing too much current?
"Best guesstimate" is that the 12V regulator is being overloaded.
You do not tell us


What Vin is for the +12V regulator
What heatsink you are using on the 12V regulator
Bonus unknown: Heatsinking on +5V regulator.


The 5V regulator with 12V in dissipates (12-5) = 7 mW/mA.
So at 140 mA power dissipation is 7 mW x 140 mA = 980 mW (if Vin remains at 12V). IF the 7805 was not heatsunk at all then it would get hot at that dissipation - so your assertion that " ...so there is no reason for them to heat up. ." is only true if thinks you have not told us allow it to be true.
Similarly, the 12V regulator dissipation depends on its Vin (unspecified), heatsinking (unspecified), stability (probably OK, but unspecified), which version of the 7812 (unspecified) - as sonme are rated at 1A+ -  and some at much less. A regulator will drop its Vout when attempts are made to cause Iout to exceed Ioutmax. 

I suggest that you load your 12V supply with a resistive load and see how it behaves across eg the 50 - 200 mA range.

Information on unknowns mentioned above will assist us to assist you.