After a fresh set up of your network, don’t be surprised that your ssh connections are slow.

Depending on the systems and equipment you use, you might encounter some timeout that make any login impossible.

I got such timeouts with an OpenBSD machine behind a Pix firewall. With Linux machines, it was very slow but worked.

This issue is related to the reverse DNS check that SSH makes by default during the login process. This is in order to improve the security. Howerver, this is not so secure as a DNS cache can also be spoofed.
Considering this, you can disable this check with not much worry with the right option in your /etc/sshd_config file :

UseDNS no

Of course, the best solution will be that you set up a full DNS infrastructure as soon as possible.