To re-generate your host keys use this command:
# ssh-keygen -t dsa -N "" -f /etc/ssh/ssh_host_dsa_key
This will re-generate the dsa keys for your host.
To re-generate the rsa keys, use the same command like this:
# ssh-keygen -t rsa -N "" -f /etc/ssh/ssh_host_rsa_key
This will generate a key pair for your system.
Also look at this link: