It is your pull up resistor (the internal pull up) you are using is at least 20K. This will not adsorbed and dissipate much noise. What it does dissipate occurs in the micro its most sensitive area for noise. I would use an external resistor at least a 5K or lower bringing the load to the switch to at least 1 mA. This will dissipate the noise outside the micro in the resistor. You could also add a snubber across the relay contacts as well.