With no other information about your network, this is a pure guess, but one of the things that will slow down an SSH (or a telnet) login is if the server to which you connect wants to do a reverse DNS lookup on the IP, and there is no reverse DNS entry for the client machine.
Could that sometimes be the case with your clients?
Regards
Neil Neil S. Briscoe
Senior Network Engineer
Zetnet Internet Services Ltd