It could be that the current flowing through the relay contacts causes a magnetic field that cancels the external field such a way that the contacts are released, the current flow stopped -> removing the cancelling field, thus causing the contacts to conduct again, i.e. having a electromechanical oscillator.
Try to change the orientation or location of the external magnet to see if that is the cause.