If you run the high-power lines close to your digital circuitry, interference can and does happen as you observed.
I noticed you do not show in your schematic any DC blocking capacitor at +Vcc (the top point). You can also use a small ~ 1 nF capacitor from base to ground, to reduce "sharp" transistor action.
If the interference still persists, I would advise to replace the transistor (or insert before it) an optocoupler (optoisolator), so the DC power circuit switched by the relay is completely insulated from your digital circuits. Maybe you should separate the power supplies, too.