I answered almost similar answer on SuperUser few days ago. The important parts:
- The format differs
- There are different host keys (types) on each server (make sure you paste the one that is actually used)
- There is
ssh-keyscan
which can create the format for you
Otherwise just prefix your key with server IP address (you can add also hostname, after comma), remove the comment from end of the line and you are fine. Format then look like this:
11.22.33.44 ssh-rsa AADGD...
And one more note, if you use HashKnownHosts yes
(Debian and Ubuntu does), you need to re-hash your known_hosts
such as:
ssh-keygen -Hf ~/.ssh/known_hosts