I've noticed my N95 8GB charger gets extremely hot very quickly and it doesn't feel normal. Should i replace it?

To be on the safe side yes i would replace it or at least find your local nokia repair center and seek their advice.

I know most chargers get warm but they should not get really hot as you describe.