Good question!! Strictly speaking, to be able to connect, you do not have to re-generate these keys. But that results in the same key fingerprinting multiple hosts, which is really not what you want: each host should have a unique fingerprint.
Re-creating them is easy: ssh-keygen
ssh-keygen -t dsa -C `uname -n` -N '' \
-f /etc/ssh/ssh_host_dsa_key
ssh-keygen -t rsa -C `uname -n` -N '' \
-f /etc/ssh/ssh_host_rsa_key
ssh-keygen -t rsa1 -C `uname -n` -N '' \
-f /etc/ssh/ssh_host_key
-- RMT
