diff --git a/ssh/handshake.go b/ssh/handshake.go
index f815cdb..653dc4d 100644
--- a/ssh/handshake.go
+++ b/ssh/handshake.go
@@ -479,10 +479,12 @@
 
 		// As a client we opt in to receiving SSH_MSG_EXT_INFO so we know what
 		// algorithms the server supports for public key authentication. See RFC
-		// 8303, Section 2.1.
-		msg.KexAlgos = make([]string, 0, len(t.config.KeyExchanges)+1)
-		msg.KexAlgos = append(msg.KexAlgos, t.config.KeyExchanges...)
-		msg.KexAlgos = append(msg.KexAlgos, "ext-info-c")
+		// 8308, Section 2.1.
+		if firstKeyExchange := t.sessionID == nil; firstKeyExchange {
+			msg.KexAlgos = make([]string, 0, len(t.config.KeyExchanges)+1)
+			msg.KexAlgos = append(msg.KexAlgos, t.config.KeyExchanges...)
+			msg.KexAlgos = append(msg.KexAlgos, "ext-info-c")
+		}
 	}
 
 	packet := Marshal(msg)