Do you know that it is the relay switched load or the relay being switched that is causing the issue? do you have diodes across the relay coils? there is another "trick" that sometimes works very well and that is to use a star grounding connection for everything. This is where all grounds go to the same point separately, not 'daisy chained' as they are now, separate ground wires for each thing connected to the board and returned to the ground that is connected to the Arduino. that way the ground current from
the relays doesn't flow through the Arduino's ground. Perhaps the best method is to use a separate PSU for the relay's so that the relay coil current doesn't come from the Arduino and thus will not affect the Arduino in either case a diode across the relay coil is required, NOT OPTIONAL. You can also try a snubber. I designed a solenoid controller for remote irrigation control and I had issues with the load resetting the Proc I found that a 4R7 ohm resistor in series with a 330 nF capacitor was a complete solution for all of the 6 or 7 different types of solenoids I had to control. It was wired across the solenoid coil terminals at the relay that I used for polarity reversal of the solenoid. In your case I would connect it across the diode you have installed across the relay coil, You DO have a dode there don't you?. You should probably add 330 - 470 uF of bypass capacitor across the 5V source where it connects to whatever you have the relays mounted on. When using an external (preferred) PSU for the relay power make certain that you connect the negative side of the external PSU to the ground on the Arduino (REQUIRED, NOT OPTIONAL).
Bob