Hi Anurag,
You mentioned 41mA per relay, so a total of about 398 mAmp at regulator input.

Here are some calculations that might be helpful:

Current going into the Regulator = 398 mAmp.
Voltage to the regulator = 12 Vdc (I am assuming here. put the actual value)

Wattage supplied to this unit = V x I = 12V x 398 mAmp = 4.776 Watts
Add a margin of 50% (for surge currents or any unavoidable condition that takes extra current)
So the total (maximum) consumption = (approx.) 7.5 Watts (max)

Assuming you are using Transformer based supply: Transformer=>DiodeBridge=>CapacitorFilters=>Regulator

The power delivered by transformer to your device = 7.5 Watts.(max)
Efficiency of Transformer = (Assuming) 40%
The Power drawn from the Mains = 7.5 Watts / 40% = (approx.) 19Watts.

Now, do you think 19 Watts of Power for your device is unacceptable? Think it over.
SMPS gives > 70% Efficiency. Re-calculate the above and see how much power your decive needs using an SMPS. This will be homework for you. If you find it difficult, post it here and that calculation will also be done for you.

Don't just go by the Current. Always consider the Power consumed by your unit. Your electricity meters are basically "Watt-Hour-Meter".