Abblockkondensator dran?
Wenn möglich einen Tiefpass in die Versorgungsspannung des AVR, also Spule oder Wiederstand mit Kondensator oder beides.
An welcher Spannung hängt überhaupt die Last? Das hört sich so an, als würde der AVR an 5V und die Last des Relais an 12V hängen.
Nen Schaltplan wäre auch nützlich.

MfG

Dennis