Here are two things that I think are important, or at least they became important for me, with configuring a debian server.
First off, the debian box I’m configuring is behind a linksys NAT firewall/router.
Secondly, the users of the system are not on the same network (they are one ip address off in the ‘private’ network, separate from the ‘public’ network)
Ok, now for the problems: logging in w/ ssh is SLOW and sending mail out is SLOW.
1) add “UseDNS no” to your /etc/ssh/sshd_config file. Then, restart ssh. This causes sshd to not perform reverse dns lookups on each host that logs in. The “slowness” is that there is no dns entry, and the lookup has to time out before it will let users log in. If the problem is still not fixed, try upgrading to a new version of your software — I’ve heard problems with PAM authentication mucking with things (and this has been fixed).
2) in /etc/exim4/exim4.conf.template, comment out the line that says “host_lookup = *” Then run update-exim4.conf and restart exim. This does the same thing as the sshd trick. You can also try changing “rfc1413_query_timeout” to “0s”
Hope this helps someone!