Off the top of my head I can think of two things that would fit the currently available information.
If, connecting to your box with ssh is slow, but when you get the shell it's usable, I would look and see if there's something with either dns and/or syslogd. I've had cases in the past where syslogd were so bogged down that logging your connection took several minutes. The other case I've had have been where reverse lookups timed out rather than returning NXDOMAIN, misconfigured dns-servers for my .in-addr.arpa zones, this goes for both syslogd, httpd and sshd.
Could you try to disable reverse-lookups for syslogd, sshd and httpd and see if that resolves your slowness ? (If it does, I would look into the dns resolver configuration and try to figure out why it's timing out on you).
The other thing that I can think of would case things to be slow could be your IO subsystem being overloaded, you would see this with tools like iostat, sar or dstat. (and possibly also increased cpu load averages).