diff --git a/ssh/agent/client_test.go b/ssh/agent/client_test.go
index a81bcd6..8ffaca7 100644
--- a/ssh/agent/client_test.go
+++ b/ssh/agent/client_test.go
@@ -182,9 +182,9 @@
 				t.Fatalf("Verify(%s): %v", pubKey.Type(), err)
 			}
 		}
-		sshFlagTest(0, ssh.SigAlgoRSA)
-		sshFlagTest(SignatureFlagRsaSha256, ssh.SigAlgoRSASHA2256)
-		sshFlagTest(SignatureFlagRsaSha512, ssh.SigAlgoRSASHA2512)
+		sshFlagTest(0, ssh.KeyAlgoRSA)
+		sshFlagTest(SignatureFlagRsaSha256, ssh.KeyAlgoRSASHA256)
+		sshFlagTest(SignatureFlagRsaSha512, ssh.KeyAlgoRSASHA512)
 	}
 
 	// If the key has a lifetime, is it removed when it should be?
diff --git a/ssh/agent/keyring.go b/ssh/agent/keyring.go
index c6eb56d..21bfa87 100644
--- a/ssh/agent/keyring.go
+++ b/ssh/agent/keyring.go
@@ -205,9 +205,9 @@
 					var algorithm string
 					switch flags {
 					case SignatureFlagRsaSha256:
-						algorithm = ssh.SigAlgoRSASHA2256
+						algorithm = ssh.KeyAlgoRSASHA256
 					case SignatureFlagRsaSha512:
-						algorithm = ssh.SigAlgoRSASHA2512
+						algorithm = ssh.KeyAlgoRSASHA512
 					default:
 						return nil, fmt.Errorf("agent: unsupported signature flags: %d", flags)
 					}
diff --git a/ssh/certs.go b/ssh/certs.go
index 6605bf6..17d4f6e 100644
--- a/ssh/certs.go
+++ b/ssh/certs.go
@@ -14,8 +14,10 @@
 	"time"
 )
 
-// These constants from [PROTOCOL.certkeys] represent the key algorithm names
-// for certificate types supported by this package.
+// Certificate algorithm names from [PROTOCOL.certkeys]. These values can appear
+// in Certificate.Type, PublicKey.Type, and ClientConfig.HostKeyAlgorithms.
+// Unlike key algorithm names, these are not passed to AlgorithmSigner and don't
+// appear in the Signature.Format field.
 const (
 	CertAlgoRSAv01        = "ssh-rsa-cert-v01@openssh.com"
 	CertAlgoDSAv01        = "ssh-dss-cert-v01@openssh.com"
@@ -25,14 +27,21 @@
 	CertAlgoSKECDSA256v01 = "sk-ecdsa-sha2-nistp256-cert-v01@openssh.com"
 	CertAlgoED25519v01    = "ssh-ed25519-cert-v01@openssh.com"
 	CertAlgoSKED25519v01  = "sk-ssh-ed25519-cert-v01@openssh.com"
+
+	// CertAlgoRSASHA256v01 and CertAlgoRSASHA512v01 can't appear as a
+	// Certificate.Type (or PublicKey.Type), but only in
+	// ClientConfig.HostKeyAlgorithms.
+	CertAlgoRSASHA256v01 = "rsa-sha2-256-cert-v01@openssh.com"
+	CertAlgoRSASHA512v01 = "rsa-sha2-512-cert-v01@openssh.com"
 )
 
-// These constants from [PROTOCOL.certkeys] represent additional signature
-// algorithm names for certificate types supported by this package.
 const (
-	CertSigAlgoRSAv01        = "ssh-rsa-cert-v01@openssh.com"
-	CertSigAlgoRSASHA2256v01 = "rsa-sha2-256-cert-v01@openssh.com"
-	CertSigAlgoRSASHA2512v01 = "rsa-sha2-512-cert-v01@openssh.com"
+	// Deprecated: use CertAlgoRSAv01.
+	CertSigAlgoRSAv01 = CertAlgoRSAv01
+	// Deprecated: use CertAlgoRSASHA256v01.
+	CertSigAlgoRSASHA2256v01 = CertAlgoRSASHA256v01
+	// Deprecated: use CertAlgoRSASHA512v01.
+	CertSigAlgoRSASHA2512v01 = CertAlgoRSASHA512v01
 )
 
 // Certificate types distinguish between host and user
@@ -433,7 +442,7 @@
 
 	if v, ok := authority.(AlgorithmSigner); ok {
 		if v.PublicKey().Type() == KeyAlgoRSA {
-			authority = &rsaSigner{v, SigAlgoRSASHA2512}
+			authority = &rsaSigner{v, KeyAlgoRSASHA512}
 		}
 	}
 
@@ -446,13 +455,11 @@
 }
 
 // certAlgoNames includes a mapping from signature algorithms to the
-// corresponding certificate signature algorithm. When a key type (such
-// as ED25516) is associated with only one algorithm, the KeyAlgo
-// constant is used instead of the SigAlgo.
+// corresponding certificate signature algorithm.
 var certAlgoNames = map[string]string{
-	SigAlgoRSA:        CertSigAlgoRSAv01,
-	SigAlgoRSASHA2256: CertSigAlgoRSASHA2256v01,
-	SigAlgoRSASHA2512: CertSigAlgoRSASHA2512v01,
+	KeyAlgoRSA:        CertAlgoRSAv01,
+	KeyAlgoRSASHA256:  CertAlgoRSASHA256v01,
+	KeyAlgoRSASHA512:  CertAlgoRSASHA512v01,
 	KeyAlgoDSA:        CertAlgoDSAv01,
 	KeyAlgoECDSA256:   CertAlgoECDSA256v01,
 	KeyAlgoECDSA384:   CertAlgoECDSA384v01,
@@ -514,7 +521,7 @@
 	return result
 }
 
-// Type returns the key name. It is part of the PublicKey interface.
+// Type returns the certificate algorithm name. It is part of the PublicKey interface.
 func (c *Certificate) Type() string {
 	algo, ok := certAlgoNames[c.Key.Type()]
 	if !ok {
diff --git a/ssh/certs_test.go b/ssh/certs_test.go
index bae7f7e..12c1afd 100644
--- a/ssh/certs_test.go
+++ b/ssh/certs_test.go
@@ -235,7 +235,7 @@
 	if !ok {
 		return nil, fmt.Errorf("invalid signer")
 	}
-	return v.SignWithAlgorithm(rand, data, SigAlgoRSA)
+	return v.SignWithAlgorithm(rand, data, KeyAlgoRSA)
 }
 
 func TestCertTypes(t *testing.T) {
@@ -248,10 +248,10 @@
 		{CertAlgoECDSA384v01, testSigners["ecdsap384"], ""},
 		{CertAlgoECDSA521v01, testSigners["ecdsap521"], ""},
 		{CertAlgoED25519v01, testSigners["ed25519"], ""},
-		{CertAlgoRSAv01, testSigners["rsa"], SigAlgoRSASHA2512},
-		{CertAlgoRSAv01, &legacyRSASigner{testSigners["rsa"]}, SigAlgoRSA},
-		{CertAlgoRSAv01, testSigners["rsa-sha2-256"], SigAlgoRSASHA2512},
-		{CertAlgoRSAv01, testSigners["rsa-sha2-512"], SigAlgoRSASHA2512},
+		{CertAlgoRSAv01, testSigners["rsa"], KeyAlgoRSASHA512},
+		{CertAlgoRSAv01, &legacyRSASigner{testSigners["rsa"]}, KeyAlgoRSA},
+		{CertAlgoRSAv01, testSigners["rsa-sha2-256"], KeyAlgoRSASHA512},
+		{CertAlgoRSAv01, testSigners["rsa-sha2-512"], KeyAlgoRSASHA512},
 		{CertAlgoDSAv01, testSigners["dsa"], ""},
 	}
 
diff --git a/ssh/client.go b/ssh/client.go
index ba8621a..43fbe25 100644
--- a/ssh/client.go
+++ b/ssh/client.go
@@ -237,11 +237,11 @@
 	// be used for the connection. If empty, a reasonable default is used.
 	ClientVersion string
 
-	// HostKeyAlgorithms lists the key types that the client will
-	// accept from the server as host key, in order of
+	// HostKeyAlgorithms lists the public key algorithms that the client will
+	// accept from the server for host key authentication, in order of
 	// preference. If empty, a reasonable default is used. Any
-	// string returned from PublicKey.Type method may be used, or
-	// any of the CertAlgoXxxx and KeyAlgoXxxx constants.
+	// string returned from a PublicKey.Type method may be used, or
+	// any of the CertAlgo and KeyAlgo constants.
 	HostKeyAlgorithms []string
 
 	// Timeout is the maximum amount of time for the TCP connection to establish.
diff --git a/ssh/client_test.go b/ssh/client_test.go
index 3063433..2814755 100644
--- a/ssh/client_test.go
+++ b/ssh/client_test.go
@@ -125,9 +125,9 @@
 		verifyAlgo string
 		wantError  string
 	}{
-		{"rsa", SigAlgoRSA, SigAlgoRSA, ""},
-		{"rsa", SigAlgoRSASHA2256, SigAlgoRSASHA2256, ""},
-		{"rsa", SigAlgoRSA, SigAlgoRSASHA2512, `ssh: invalid signature algorithm "ssh-rsa", expected "rsa-sha2-512"`},
+		{"rsa", KeyAlgoRSA, KeyAlgoRSA, ""},
+		{"rsa", KeyAlgoRSASHA256, KeyAlgoRSASHA256, ""},
+		{"rsa", KeyAlgoRSA, KeyAlgoRSASHA512, `ssh: invalid signature algorithm "ssh-rsa", expected "rsa-sha2-512"`},
 		{"ed25519", KeyAlgoED25519, KeyAlgoED25519, ""},
 	} {
 		key := testSigners[tt.key].PublicKey()
diff --git a/ssh/common.go b/ssh/common.go
index 9dda7e5..768641f 100644
--- a/ssh/common.go
+++ b/ssh/common.go
@@ -69,13 +69,13 @@
 // supportedHostKeyAlgos specifies the supported host-key algorithms (i.e. methods
 // of authenticating servers) in preference order.
 var supportedHostKeyAlgos = []string{
-	CertSigAlgoRSASHA2512v01, CertSigAlgoRSASHA2256v01,
-	CertSigAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01,
+	CertAlgoRSASHA512v01, CertAlgoRSASHA256v01,
+	CertAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01,
 	CertAlgoECDSA384v01, CertAlgoECDSA521v01, CertAlgoED25519v01,
 
 	KeyAlgoECDSA256, KeyAlgoECDSA384, KeyAlgoECDSA521,
-	SigAlgoRSASHA2512, SigAlgoRSASHA2256,
-	SigAlgoRSA, KeyAlgoDSA,
+	KeyAlgoRSASHA512, KeyAlgoRSASHA256,
+	KeyAlgoRSA, KeyAlgoDSA,
 
 	KeyAlgoED25519,
 }
@@ -92,20 +92,20 @@
 // hashFuncs keeps the mapping of supported algorithms to their respective
 // hashes needed for signature verification.
 var hashFuncs = map[string]crypto.Hash{
-	SigAlgoRSA:               crypto.SHA1,
-	SigAlgoRSASHA2256:        crypto.SHA256,
-	SigAlgoRSASHA2512:        crypto.SHA512,
-	KeyAlgoDSA:               crypto.SHA1,
-	KeyAlgoECDSA256:          crypto.SHA256,
-	KeyAlgoECDSA384:          crypto.SHA384,
-	KeyAlgoECDSA521:          crypto.SHA512,
-	CertSigAlgoRSAv01:        crypto.SHA1,
-	CertSigAlgoRSASHA2256v01: crypto.SHA256,
-	CertSigAlgoRSASHA2512v01: crypto.SHA512,
-	CertAlgoDSAv01:           crypto.SHA1,
-	CertAlgoECDSA256v01:      crypto.SHA256,
-	CertAlgoECDSA384v01:      crypto.SHA384,
-	CertAlgoECDSA521v01:      crypto.SHA512,
+	KeyAlgoRSA:           crypto.SHA1,
+	KeyAlgoRSASHA256:     crypto.SHA256,
+	KeyAlgoRSASHA512:     crypto.SHA512,
+	KeyAlgoDSA:           crypto.SHA1,
+	KeyAlgoECDSA256:      crypto.SHA256,
+	KeyAlgoECDSA384:      crypto.SHA384,
+	KeyAlgoECDSA521:      crypto.SHA512,
+	CertAlgoRSAv01:       crypto.SHA1,
+	CertAlgoRSASHA256v01: crypto.SHA256,
+	CertAlgoRSASHA512v01: crypto.SHA512,
+	CertAlgoDSAv01:       crypto.SHA1,
+	CertAlgoECDSA256v01:  crypto.SHA256,
+	CertAlgoECDSA384v01:  crypto.SHA384,
+	CertAlgoECDSA521v01:  crypto.SHA512,
 }
 
 // unexpectedMessageError results when the SSH message that we received didn't
diff --git a/ssh/handshake.go b/ssh/handshake.go
index 05ad49c..5eeddb3 100644
--- a/ssh/handshake.go
+++ b/ssh/handshake.go
@@ -460,9 +460,9 @@
 			algo := k.PublicKey().Type()
 			switch algo {
 			case KeyAlgoRSA:
-				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{SigAlgoRSASHA2512, SigAlgoRSASHA2256, SigAlgoRSA}...)
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{KeyAlgoRSASHA512, KeyAlgoRSASHA256, KeyAlgoRSA}...)
 			case CertAlgoRSAv01:
-				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{CertSigAlgoRSASHA2512v01, CertSigAlgoRSASHA2256v01, CertSigAlgoRSAv01}...)
+				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, []string{CertAlgoRSASHA512v01, CertAlgoRSASHA256v01, CertAlgoRSAv01}...)
 			default:
 				msg.ServerHostKeyAlgos = append(msg.ServerHostKeyAlgos, algo)
 			}
@@ -629,11 +629,11 @@
 			// so we have to manually check for a compatible host key.
 			switch kt {
 			case KeyAlgoRSA:
-				if algs.hostKey == SigAlgoRSASHA2256 || algs.hostKey == SigAlgoRSASHA2512 {
+				if algs.hostKey == KeyAlgoRSASHA256 || algs.hostKey == KeyAlgoRSASHA512 {
 					hostKey = &rsaSigner{signer, algs.hostKey}
 				}
 			case CertAlgoRSAv01:
-				if algs.hostKey == CertSigAlgoRSASHA2256v01 || algs.hostKey == CertSigAlgoRSASHA2512v01 {
+				if algs.hostKey == CertAlgoRSASHA256v01 || algs.hostKey == CertAlgoRSASHA512v01 {
 					hostKey = &rsaSigner{signer, certToPrivAlgo(algs.hostKey)}
 				}
 			}
diff --git a/ssh/keys.go b/ssh/keys.go
index c67d3a3..17b46a4 100644
--- a/ssh/keys.go
+++ b/ssh/keys.go
@@ -30,8 +30,9 @@
 	"golang.org/x/crypto/ssh/internal/bcrypt_pbkdf"
 )
 
-// These constants represent the algorithm names for key types supported by this
-// package.
+// Public key algorithms names. These values can appear in PublicKey.Type,
+// ClientConfig.HostKeyAlgorithms, Signature.Format, or as AlgorithmSigner
+// arguments.
 const (
 	KeyAlgoRSA        = "ssh-rsa"
 	KeyAlgoDSA        = "ssh-dss"
@@ -41,16 +42,21 @@
 	KeyAlgoECDSA521   = "ecdsa-sha2-nistp521"
 	KeyAlgoED25519    = "ssh-ed25519"
 	KeyAlgoSKED25519  = "sk-ssh-ed25519@openssh.com"
+
+	// KeyAlgoRSASHA256 and KeyAlgoRSASHA512 are only public key algorithms, not
+	// public key formats, so they can't appear as a PublicKey.Type. The
+	// corresponding PublicKey.Type is KeyAlgoRSA. See RFC 8332, Section 2.
+	KeyAlgoRSASHA256 = "rsa-sha2-256"
+	KeyAlgoRSASHA512 = "rsa-sha2-512"
 )
 
-// These constants represent non-default signature algorithms that are supported
-// as algorithm parameters to AlgorithmSigner.SignWithAlgorithm methods. See
-// [PROTOCOL.agent] section 4.5.1 and
-// https://tools.ietf.org/html/draft-ietf-curdle-rsa-sha2-10
 const (
-	SigAlgoRSA        = "ssh-rsa"
-	SigAlgoRSASHA2256 = "rsa-sha2-256"
-	SigAlgoRSASHA2512 = "rsa-sha2-512"
+	// Deprecated: use KeyAlgoRSA.
+	SigAlgoRSA = KeyAlgoRSA
+	// Deprecated: use KeyAlgoRSASHA256.
+	SigAlgoRSASHA2256 = KeyAlgoRSASHA256
+	// Deprecated: use KeyAlgoRSASHA512.
+	SigAlgoRSASHA2512 = KeyAlgoRSASHA512
 )
 
 // parsePubKey parses a public key of the given algorithm.
@@ -325,11 +331,9 @@
 type AlgorithmSigner interface {
 	Signer
 
-	// SignWithAlgorithm is like Signer.Sign, but allows specification of a
-	// non-default signing algorithm. See the SigAlgo* constants in this
-	// package for signature algorithms supported by this package. Callers may
-	// pass an empty string for the algorithm in which case the AlgorithmSigner
-	// will use its default algorithm.
+	// SignWithAlgorithm is like Signer.Sign, but allows specifying a desired
+	// signing algorithm. Callers may pass an empty string for the algorithm in
+	// which case the AlgorithmSigner will use a default algorithm.
 	SignWithAlgorithm(rand io.Reader, data []byte, algorithm string) (*Signature, error)
 }
 
@@ -383,11 +387,11 @@
 func (r *rsaPublicKey) Verify(data []byte, sig *Signature) error {
 	var hash crypto.Hash
 	switch sig.Format {
-	case SigAlgoRSA:
+	case KeyAlgoRSA:
 		hash = crypto.SHA1
-	case SigAlgoRSASHA2256:
+	case KeyAlgoRSASHA256:
 		hash = crypto.SHA256
-	case SigAlgoRSASHA2512:
+	case KeyAlgoRSASHA512:
 		hash = crypto.SHA512
 	default:
 		return fmt.Errorf("ssh: signature type %s for key type %s", sig.Format, r.Type())
@@ -979,12 +983,12 @@
 	if _, ok := s.pubKey.(*rsaPublicKey); ok {
 		// RSA keys support a few hash functions determined by the requested signature algorithm
 		switch algorithm {
-		case "", SigAlgoRSA:
-			algorithm = SigAlgoRSA
+		case "", KeyAlgoRSA:
+			algorithm = KeyAlgoRSA
 			hashFunc = crypto.SHA1
-		case SigAlgoRSASHA2256:
+		case KeyAlgoRSASHA256:
 			hashFunc = crypto.SHA256
-		case SigAlgoRSASHA2512:
+		case KeyAlgoRSASHA512:
 			hashFunc = crypto.SHA512
 		default:
 			return nil, fmt.Errorf("ssh: unsupported signature algorithm %s", algorithm)
diff --git a/ssh/keys_test.go b/ssh/keys_test.go
index d64ef73..334ef74 100644
--- a/ssh/keys_test.go
+++ b/ssh/keys_test.go
@@ -145,7 +145,7 @@
 
 			// RSA keys are the only ones which currently support more than one signing algorithm
 			if pub.Type() == KeyAlgoRSA {
-				for _, algorithm := range []string{SigAlgoRSA, SigAlgoRSASHA2256, SigAlgoRSASHA2512} {
+				for _, algorithm := range []string{KeyAlgoRSA, KeyAlgoRSASHA256, KeyAlgoRSASHA512} {
 					signWithAlgTestCase(algorithm, algorithm)
 				}
 			}
diff --git a/ssh/server.go b/ssh/server.go
index bf5364c..e70c592 100644
--- a/ssh/server.go
+++ b/ssh/server.go
@@ -120,7 +120,7 @@
 }
 
 // AddHostKey adds a private key as a host key. If an existing host
-// key exists with the same algorithm, it is overwritten. Each server
+// key exists with the same public key format, it is replaced. Each server
 // config must have at least one host key.
 func (s *ServerConfig) AddHostKey(key Signer) {
 	for i, k := range s.hostKeys {
@@ -284,7 +284,7 @@
 
 func isAcceptableAlgo(algo string) bool {
 	switch algo {
-	case SigAlgoRSA, SigAlgoRSASHA2256, SigAlgoRSASHA2512, KeyAlgoDSA, KeyAlgoECDSA256, KeyAlgoECDSA384, KeyAlgoECDSA521, KeyAlgoSKECDSA256, KeyAlgoED25519, KeyAlgoSKED25519,
+	case KeyAlgoRSA, KeyAlgoRSASHA256, KeyAlgoRSASHA512, KeyAlgoDSA, KeyAlgoECDSA256, KeyAlgoECDSA384, KeyAlgoECDSA521, KeyAlgoSKECDSA256, KeyAlgoED25519, KeyAlgoSKED25519,
 		CertAlgoRSAv01, CertAlgoDSAv01, CertAlgoECDSA256v01, CertAlgoECDSA384v01, CertAlgoECDSA521v01, CertAlgoSKECDSA256v01, CertAlgoED25519v01, CertAlgoSKED25519v01:
 		return true
 	}
diff --git a/ssh/session_test.go b/ssh/session_test.go
index fbec952..a4e1a59 100644
--- a/ssh/session_test.go
+++ b/ssh/session_test.go
@@ -757,11 +757,11 @@
 	connect(clientConf, KeyAlgoECDSA256)
 
 	// Client asks for RSA explicitly.
-	clientConf.HostKeyAlgorithms = []string{SigAlgoRSA}
+	clientConf.HostKeyAlgorithms = []string{KeyAlgoRSA}
 	connect(clientConf, KeyAlgoRSA)
 
 	// Client asks for RSA-SHA2-512 explicitly.
-	clientConf.HostKeyAlgorithms = []string{SigAlgoRSASHA2512}
+	clientConf.HostKeyAlgorithms = []string{KeyAlgoRSASHA512}
 	// We get back an "ssh-rsa" key but the verification happened
 	// with an RSA-SHA2-512 signature.
 	connect(clientConf, KeyAlgoRSA)
diff --git a/ssh/testdata_test.go b/ssh/testdata_test.go
index 83aa51b..26fe248 100644
--- a/ssh/testdata_test.go
+++ b/ssh/testdata_test.go
@@ -37,9 +37,9 @@
 		if v, ok := testSigners[t].(*rsaSigner); ok {
 			switch t {
 			case "rsa-sha2-256":
-				testSigners[t] = &rsaSigner{v, SigAlgoRSASHA2256}
+				testSigners[t] = &rsaSigner{v, KeyAlgoRSASHA256}
 			case "rsa-sha2-512":
-				testSigners[t] = &rsaSigner{v, SigAlgoRSASHA2512}
+				testSigners[t] = &rsaSigner{v, KeyAlgoRSASHA512}
 			}
 		}
 		if err != nil {