You should use 'slogin -v' and see which step is slow.
One possible problem is DNS timeouts.

SSH version 2 does a DH key exchange, and then authenticates the
exchange/user.  Symmetric encryption is fast, even on really slow
machines.  I presume login is slow, and then typing/echoing is quick.

You did not give the hardware on both ends.  From a 933 MHz PIII to a
100 MHz Sparcstation 20, with 2048 bit DH keys, it takes about 6
seconds to do 'ssh -2 -v other.machine.org id'.  The sparc is the slow
half in this exchange (although I built openssl with -mv8 or some
such).  Your 233 MHz Pentium should be at least this fast.  Asumming
it is a P5 and not a P6, I'd expect more like 1-2s with 2048 bit keys.

See /etc/moduli on both ends.  At least at some point in the past, the
default was to do a 4096-bit DH exchange.  I don't understand the
negotiation to determine key size, or how it avoids an attacker
manipulating it to a low value, but if you remove the > 2048 bit lines
in /etc/moduli, you will see smaller keys and faster connections.

Examine the output from -v; the following shows a 2049-bit group:

  debug1: SSH2_MSG_KEXINIT sent
  debug1: SSH2_MSG_KEXINIT received
  debug1: kex: server->client aes128-cbc hmac-md5 none
  debug1: kex: client->server aes128-cbc hmac-md5 none
  debug1: SSH2_MSG_KEX_DH_GEX_REQUEST sent
  debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP
  debug1: dh_gen_key: priv key bits set: 127/256
  debug1: bits set: 1050/2049
  debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
  debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY
  debug1: Host 'other.machine.org' is known and matches the DSA host key.
  debug1: Found key in /home/foo/.ssh/known_hosts:5
  debug1: bits set: 998/2049
  debug1: ssh_dss_verify: signature correct
  debug1: kex_derive_keys

How much key you need is an interesting question.  It depends on your
threat model, really.  I would be surprised if using a 2048-bit group
were the weak link in most systems.

        Greg Troxel <gdt@ir.bbn.com>