Maybe this doesn't have to do with the authentication, but rather DNS. 
Could it be that it takes a while to resolve your machine?  if you do ssh
-v you'll probably see where it hangs.


>> Just a reality check.
>>
>> I'm using the Public/Private DSA key authentication for SSH on a
>> 233MHz Pentium box (128MB RAM) running NetBSD 1.5.2. When I execute
>> ssh <machine>, or slogin <machine>, it takes about 10 seconds for my
>> NetBSD box to repsond.
>>
>> I just assuming it's taking this long to process the 128-bit
>> encryption. However, I'm running Suse Linux on a 433MHz PII box, and
>> it responds almost instantly.