My Linux(UbuntuEEE) to Linux(CentOS) ssh takes a long time to log in(~15 seconds) when using the private interface, but not when using the public one.

I have a Linux box acting as my router. As such, it has multiple interfaces(75.xxx.xxx.xxx, 192.168.1.1). I can ssh in from the internal interface(192.168.1.65 to .1), but it will take a while. I can ssh into the public address, and it goes quickly(~1 second).

I have another box that I can ssh into the inside interface from and it goes quickly.

iptables is set to accept packets coming into the interface immediately. sshd's UseDNS is normally on; I get the same problem if I turn it off and restart sshd. I normally use public-key authentication; I have done a mv ~/.ssh/ ~/ssh/ and it will ask me for a password after going slowly.

After logging in(using either interface), speed is quick.

ssh client version(via ssh -v):OpenSSH_4.7p1 Debian-8ubuntu1.2, OpenSSL 0.9.8g 19 Oct 2007
ssh server version(via rpm -qv openssh_server):openssh-server-4.3p2-29.el5