[ale] SSH key question

[John Mills]

ALErs -

One way I access a remote SSH login is through a 2-way NAT setup that 
assigns out-going and incoming hosts' addresses against pools (or some 
other algorithm) so my identity at the remote end is something like 
<my_username>@<random_hostname_or_IP>.<their_domain>. I tried storing my 
originating account's public keys in my remote server's 
'~/.ssh/authorized_keys', but since the originating host appears to float 
they are not used. Same problem at the originating end: it looks as though 
I'm connecting to a different server every few times I connect.

For practical purposes this looks like "man-in-the-middle" all day, every 
day -- doesn't give a warm feeling.

How can I set up an encrypted, shared-key login in this type environment?

Thanks.

  - Mills