sshd needs long time to authenticate

Hi out there, we are using Suse Linux 8.1 for our server and need OpenSSH to log in from other locations. We decided to use protocol version 2 with private/public key login and passphrases. It works all fine, but it needs about 2 min to authenticate. When we work with passwords it needs just a second and it makes no difference if I'm in the office or in outer space. Is there anybody who has an idea to short this long time ? Thanks Dieter Brockmeyer