fwiw, i haven't had any lockups, but ssh'ing from my 270mhz ultra5, it takes much longer for the passwd prompt to appear than it does from even an old 166mhz pentium.
Same here, my Debian Ultra 60 has the slowest ssh-login on all the machines I can login to. I've had a look at the logfiles and made a verbose login but couldn't find anything. But the thing about not enough entropy is an interesting thought. The installation is very much stripped down with only the most necessary things running. No X, no mouse, no unnecessary daemons... Got to dig a bit deeper into that.
Arthur