This is an unusual topic since most distribution create these keys for you during the installation of the OpenSSH server package. But it may be useful to be able generate new server keys from time to time, this happen to me when I duplicate Virtual Private Server which contains an installed ssh package.

OpenSSH require different keys depending if you use SSH1 and/or SSH2 protocol. All keys are generated by ssh-keygen, that one should be available on your system with the ssh package. The receipt is almost the same as for generating your own keys, except that you should use an empty passphrase. Default key lengths are also appropriate (2048 bits for rsa and 1024 bits for dsa)

SSH1 protocol

For SSH1 protocol, you need a rsa1 key generated has follow:

ssh-keygen -q -f /etc/ssh/ssh_host_key -N '' -t rsa1

SSH2 protocol

For SSH2 protocol, you need two keys, one RSA key and one DSA key generated has follow:

ssh-keygen -f /etc/ssh/ssh_host_rsa_key -N '' -t rsa
ssh-keygen -f /etc/ssh/ssh_host_dsa_key -N '' -t dsa

Since January 2011, OpenSSH also support ECDSA key, you may generate a new one using:

ssh-keygen -f /etc/ssh/ssh_host_ecdsa_key -N '' -t ecdsa -b 521