Depends on paper (Agfa was terrible for fogging) and storage conditions (temperature, humidity and presence of sulfides). I have some 4-year-old Kentmere and Ilford that's perfect (no refrigeration but always indoors)... but 1996 was a long time ago and you will have to test.
If they haven't been stored in the fridge up to now, putting them in the fridge now is pointless. If you're going to use them in the next year or three, refrigeration is irrelevant even if they've been stored cold their entire life. Don't waste the space on such old paper.