Assuming you are using the 5V versions of the family of relays you've linked (005-360), the coil resistance is between 62.1 and 75.9 ohms. Under 5V, that's 81mA each, so you shouldn't have any problem powering 5 of these (403mA) on the current limit side: the 7805CV is internally limited to 750mA typical (1.2A max).
However, depending on your casing, the temperature overload protection might activate: for a T0-220 for example, the thermal resistance junction to ambient is 50°C/W and you're dissipating 5V x 400mA with 5 of them which yields a temperature increment of 100°C with respect to ambient. The thermal resistances are approximate, so that might put it beyond the 150°C limit (which also may be set lower).
Nonetheless this is for 5, it should not be a problem for 3 except if the thermal limit is really lower than operating range. If you want to add a current limiting resistor, beware of the pickup voltage which is 3.75V: any less voltage on the coil and it won't be able to pick up the contact. That means the resistor shall not be more than 20 ohms otherwise the voltage divider will leave less voltage for the coil (be sure to use at least >0.25W resistors). But I would suggest first to measure the voltage delivered by the 7805 while touching it briefly (caution, it may burn!). Then make sure that pickup voltage is really 3.75V by gradually increasing the applied voltage in order to select your current limiting resistor.
Also, you're not actually giving 5V, but 4.3V since the diodes are in series. Not only that but they can't fulfill their job which is to allow the current that can't briefly stop in the inductor to loop around: put them in parallel with the coils instead of in series. Otherwise, the coil will resist switch-OFF by producing a massive voltage between its terminals which may damage the transistor, the diode, or even the regulator.
The relays you're using aren't sealed, and over time - depending on the environment in which they're being stored/used - their contacts can become oxidized or contaminated with chlorine or sulfur, causing their closed resistance to become higher than specified on the data sheet.
If light, the corrosion can usually be blasted away and the native silver alloy exposed by hot-switching the contacts at their maximum rated voltage and current. If that doesn't work, then the contacts must be mechanically cleaned.
The reason these relays are failing for you is because their contacts are made from a silver alloy especially formulated to switch highish power, and the low power levels you're using don't have enough "oomph" to blast off the contact contamination and get down to the bare metal. For reliable operation and maximum life of the relay you should switch to a relay designed to handle signal-level power, and it should be hermetically sealed.
For your perusal:
Best Answer
Unless you can guarantee that all the contacts will close and open at exactly the same instant of time the only safe current you can assume is 2A - that is, the capacity of the first contacts to close, or the last contacts to separate.