This is Ubuntu/Debian centric so it may not work for others:

<code>
sudo rm /etc/ssh/ssh_host_{dsa,rsa}_key*

sudo dpkg-reconfigure -plow openssh-server
</code>

Or the old fashion way:

<code> 
 ssh-keygen -b 4096 -t rsa -f ssh_host_rsa_key
</code>