How to generate ssh host keys in a linux machine

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:
http://www.ssh.com/support/documentation/online/ssh/adminguide/32/Generating_the_Host_Key.html