I don't run relay coils off a voltage regulator. Use 12V relays instead, powered off the raw DC.
Relays are quite tolerant of their coil voltage being imprecise, after all they are just a big resistor made of copper wire.
If you must use 5V relays, you can do PWM to lower holding current, 50% PWM.