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