Copy ssh keys from one server to another server

As Ethabell mentioned, you can copy over the current host keys to the new server.

You can find your host keys by opening your sshd_config file (On my Ubuntu 12.04 box its /etc/ssh/sshd_config). In the config file look for the HostKey entries. These entries will tell you where the host key files are located. You should be able to copy these files to the new server and update the new server's sshd_config to point to the copied keys (or just overwrite the files that already exist on the new server).

Also, note this section from the sshd_config man page, specifically the part about permissions:

Specifies a file containing a private host key used by SSH. The default is /etc/ssh/ssh_host_key for protocol version 1, and /etc/ssh/ssh_host_dsa_key, /etc/ssh/ssh_host_ecdsa_key and /etc/ssh/ssh_host_rsa_key for protocol version 2. Note that sshd(8) will refuse to use a file if it is group/world-accessible. It is possible to have multiple host key files. “rsa1” keys are used for version 1 and “dsa”, “ecdsa” or “rsa” are used for version 2 of the SSH protocol.