====== slow ssh connections ======
You can debug your ssh connection by adding the -v switch.  If the solutions below aren't helping, you at least have better search terms for google.

===== dns =====
Make sure an entry exists for both the client and server in your dns server, or in /etc/hosts.