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

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

sudo dpkg-reconfigure -plow openssh-server

Or the old fashion way:

 
 ssh-keygen -b 4096 -t rsa -f ssh_host_rsa_key