On the server, /etc/ssh/ssh_host_rsa_key.pub is the public half of /etc/ssh/ssh_host_rsa_key, also on the server. The client will not have the private half of that key. If you are connecting to the server with ssh V2 (the default), then changing this key on the server will change it's fingerprint. You can change the key with:
Changing the public key half alone will not change anything about the server. Only changing the private key on the server will change its fingerprint.
sudo sh-keygen -q -f /etc/ssh/ssh_host_rsa_key -N '' -t rsa
You can get apt-get to do all of this for you on the server _without_ reinstalling the whole machine like this:
As I said before, if the problem is that you have a bad key in ~/.ssh/known_hosts in your user account on the client, then changing the key on the server will not help, because you'll still have a bad key in known_hosts on the client.
sudo aptitude purge openssh-server
sudo aptitude install openssh-server