SSH into NAT'd servers on the same public IP address

I am trying to SSH from in office X to a few Linux boxes in office Y. The Linux boxes in office Y are behind NAT and each run on their own ports. I can successfully reach all of them through SSH, but I cannot authenticate.

I was able to SSH into the first box, but when I got to the second it said:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
[edited out fingerprint]
Please contact your system administrator.
Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending key in /root/.ssh/known_hosts:1

My understanding is that it is expecting to see the same key from that public IP address, but it is seeing a different one because it's a different SSH server.

How can I fix it so it creates/accepts a different key from each server behind that same IP address?

The hostname or IP address is being stored as a hash (or in plain text depending on options and version defaults) in your known_hosts file. The easiest workaround is to add an entry for each host to DNS or /etc/hosts (ugh!) file with the same IP (WAN) address such as in /etc/hosts:

your.wan.ip.address      servera serverb

and then ssh by hostname and port.

There are a few ways of fixing this:

1. You can disable host key checking for this particular host. In your ssh_config file (~/.ssh/config), put something like:

   Host remote.host.name
   UserKnownHostsFile /dev/null
   StrictHostkeyChecking no
   

   This configures ssh to never store host keys for remote.host.name, but the downside is that now you are open to man-in-the-middle attacks (because you are blindly accepting host keys you can't tell if the remote host key has changed).

2. You can use a similar technique to simply give each a host a unique known_hosts file:

   Host hosta
   Port 10098
   Hostname remote.host.name
   UserKnownHostsFile ~/.ssh/known_hosts_hosta
   
   Host hostb
   Port 10099
   Hostname remote.host.name
   UserKnownHostsFile ~/.ssh/known_hosts_hostb
   

   You will then connect to these hosts with ssh hosta or ssh hostb, and ssh will take the actual hostname and port from the conciguration file.

You don't say which version of Solaris (and, more importantly, SSH) you're using, but sufficiently up-to-date versions of OpenSSH have addressed this problem.

Here are two entries from my known_hosts file, which have the same IP address but different port numbers (one is the implicit 22); as you can see the stored keys are not the same.

[10.69.55.47]:2222 ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEAo+zenWwhFWAa/exdxbm3A3htDFGwFVjFlHLO83AfOaloBbBrr6whmLeDqVPBSwI/yrePClpahLUMYE6qGBFCbbOYiQkMDwacNFfxvxd6oCMDDqZH6NWGiBCt0b2M6YKYhYCw6z8n0yvlLk1eTdpp2OpjbfwAIe4eBkWyKNZY9+17VtzARqGR9tgHC8Dh7HBApDR8wooc+XzY6FhD2b21meIt8r8bjfBIu5t6eQgDHh/TzUT1rGH6W0HeUJxpDnpud5Af1ygMEQFrGrzHi5HKtg+K6HFBggMF8t6p2Dz8oMds5pi6IuPlVi3UvO1X7mMJ9pP7ByMQqiVrQ9wtAbC2QQ==
10.69.55.47 ssh-rsa AAAAB3NzaC1yc2EAAAABIwAAAQEA1clJ6vp8NDy7D9YVgAKQQzERfx3scR0c0027yOYGGpeLg+nW+x8mJk1ia9GouUTDME+NP2YDVZUEDog9rtTJvuLd22ZxfoC8LGboyBsmlhOVxdSCxmA/+blPCp1pyocr8pXyXjSkb/qQKKQMRoAU7qKKHPfI5Vugj04l6WbW2rJQTqFD/Lguc8AAUOE6K4DNhETOH2gOnwq6xi0vutDmeUKSqEvM/PQFZSlOL4dFDYO5jAUjvgm6yGHP3LlS9fmCzayJgGgLSnNz0nlcd94Pa1Cd441cCAZHFDvDPniawEafH9ok4Mmew0UGopQGUGbfb5+8g8YphLW6aLdrvnZbAw==

I don't know which version of OpenSSH introduced this, but I'm running

[me@risby fin]$ ssh -V
OpenSSH_6.9p1, OpenSSL 1.0.1k-fips 8 Jan 2015

To expand on my comment to @larsks answer, I think using ~/.ssh/config entries is much better than modifying /etc/hosts, though I would use the HostKeyAlias rather than splitting out the known hosts to different files. e.g:

Host hosta
Port 10098
Hostname remote.host.name
HostKeyAlias hosta

And similarly for hostb