> If I try to ssh over, using "sh -vvv hostname" from my Linux box, the
>process stalls for roughly five minutes on:
>
>   debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY

I had the same problem SSHing into a Quadra 610 (25Mhz 040), coming from 
OS X. The only solution I found was to force SSH1 mode in OS X, then the 
stall goes away.

This seemed to be specific to the version of OpenSSH in OS X, as a 
standalone SSH2 client on OS 9 worked without significant delay. Putty in 
Windows doesn't seem to have the delay problem either.

So I'm wondering if your Linux machine has a similar version of OpenSSH 
as OS X does (or maybe the same bug, or "feature" that is causing it).

> Then it proceeds, but I wasn't able to ssh as root; even given the right
>password, it denied me. I didn't have time to try a regular user; it might
>be configured to deny remote root logins.

I didn't experience any other problems beyond the delay. Once I let it 
sit and complete the login, everything else worked fine. So maybe on this 
issue it is just that you have remote root disabled.

>The main question I have is, is
>the five-minute delay inevitable on an SE/30? It happens the same way
>ssh'ing *out* from the SE/30, too. Is there anything I can do to speed
>things up?

Try forcing SSH 1 mode. See if that speeds it up. That is the only 
solution I found to work with OS X's SSH client. In mode 1, there is no 
significant delay that I notice, nothing more than 2 or 3 seconds to 
complete the logon. (I've never tried SSHing out from my Q610, so I don't 
know if there is a delay that direction).

-chris
<http://www.mythtech.net>