When I ssh to my box, an Ultra 5. I get prompted for password immediately. I enter it and have to wait sometimes a full minute for it to prompt for a password.
The same thing happens when i try to ftp to the box, it will say connected, but it takes forever to prompt for password, and sometimes login too.
Once in the box, it works fine, commands run quick etc... I have no idea why this is happening. I'm running Openssh 3.9, Solaris 9, all patches are up to date.

Any insight as to why this may be?

My inclination would be to say that you have either a routing, or more likely a name resoluation issue, but it could also be that you have an auto-negotiation problem.

Check your nsswitch.conf, resolv.conf and routing information. If you can find nothing wrong there, try forcing autonegotiation, by using ndd to set the tunable adv_autoneg_cap to 1 for your network interface.

add your workstation ip and name in your Sun box /etc/hosts file