Perts,
That attempt to suddenly stop the current flow is what generates a large voltage transient. If you can, you would be better off to place a diode across the inductor (called a freewheeling or flywheel diode) to suppress the voltage spikes. The diode should have a forward voltage rating of at least the maxmium voltage (preferably higher) of the circuit, and a minimum continuous rating of six amperes. This diode will allow the current to decrease based on the L/R time constant of the inductor. It should also minimize the arcing at the relay contacts. As the circuit response will be slower, make certain that the addition of this diode does not compromise any safety aspect of the circuit.
Hope this helps,
Raisinbran