Forget the relay drivers that MarkDerbyshire mentioned. You already have them. You have a two for one, in the optoisolators. You get opto isolation between the relay board and the Arduino output as well as the relay driver (current multiplier).
You posted a link to the board that includes the schematic. Take some time to review the schematic. Now that you are making me explain it, I realized I was mistaken. The Arduino pin does not directly drive the relay and the optoisolator. The JD-Vcc jumper just separates power for the optoisolator from the power for the relays. You can try it, but I'm not hopeful it will change anything. Recall when you wanted to add a second Vcc line to the relay board. I told you to do the same thing, but from the perspective of the relay board. (you said push, I said pull).
The 7805 is a much better option. Don't forget to connect the ground of the 7805 to both the arduino, the 12V power supply and the relay board.