Slow connection performance - ssh2

[David M. Gibson]

Using ssh2 via agent to connect through proxy to sshd host. Each
connection (client to proxy, proxy to host) takes an average of 22
seconds, totaling approximately 44 seconds for a complete connection.
Debug logging with vmstat directed to the same file indicates two points
where a majority of time is spent (have looked at the similar postings):

debug1: expecting SSH2_MSG_KEX_DH_GEX_GROUP (*6 seconds*)
0 0 0 0 13236 0 8248 0 0 0 0 242 88 21 8 71
1 0 0 0 13236 0 8248 0 0 0 0 239 70 64 2 35
3 0 0 0 13084 0 8248 0 0 0 0 122 92 84 16 0
1 0 0 0 13352 0 8248 0 0 0 0 123 693 79 21 0
1 0 0 0 13352 0 8248 0 0 0 0 117 64 98 2 0
4 0 0 0 13252 0 8248 0 0 0 0 117 77 95 5 0
debug1: dh_gen_key: priv key bits set: 179/384
debug1: bits set: 2042/4095
debug1: SSH2_MSG_KEX_DH_GEX_INIT sent
debug1: expecting SSH2_MSG_KEX_DH_GEX_REPLY (*7 seconds*)
1 0 0 0 13336 0 8248 0 0 0 0 174 117 36 28 36
debug3: check_host_in_hostfile: filename /root/.ssh/known_hosts
debug3: check_host_in_hostfile: match line 16
debug1: Host '10.1.1.1' is known and matches the RSA host key.
debug1: Found key in /root/.ssh/known_hosts:16
debug1: bits set: 2057/4095
1 0 0 0 13320 0 8248 0 0 0 0 267 60 69 2 29
2 0 0 0 13304 0 8248 0 0 0 0 121 74 100 0 0
1 0 0 0 13332 0 8248 0 0 0 0 123 218 74 26 0
1 0 0 0 13332 0 8248 0 0 0 0 122 68 97 3 0
1 0 0 0 13332 0 8248 0 0 0 0 122 70 98 2 0
2 0 0 0 13188 0 8248 0 0 0 0 124 130 69 31 0
debug1: ssh_rsa_verify: signature correct

Using rsa and have tested both 2048-bit and 1024-bit keys. Implemented
the key size incrementally (target server first (aix), client(linux),
then proxy(RH linux)) and did not see any difference in connection time.

I am curious about the "bits set 20nn/4095" which also seems to be
consist (although the nn vary by +/- 10-20) across the combination of
tests as we transitioned from 2048 bit keys on all three devices to a
mixture of 2048 & 1024 keys to 1024 on all three devices.

What does the "bits set" size indicate, is it related to the size of
key?

Is there a way to influence this so less cpu is consumed on the client? 

The client is an i386 device running at 100Mhz using dialup to connect
proxy and then ethernet to target host server. 

Are there any optimizations/considerations for this platform?

David M. Gibson