I've tried various method to debug, looking into all sort of possible network issues. I set LookupClientHostnames to no. I even tried UseDNS no but the SSH that came with Solaris 10 doesn't recognize that command. BEWARE!! UseDNS in your sshd_config file will cause SSH to not be able to start!
At the end, I decided to time my startup script in /etc/profile
It appears that /usr/sbin/quota takes more than 20s to run. So the solution was to either modify /etc/profile and /etc/.login, or to do a touch .hushlogin in the user's home directory.
I opted for the latter.
