For example, according to RFC4253, "ssh-rsa" is a key format where the server generates an RSA keypair. So far, so good. However, I don't seem to understand where SHA-1 comes into the play.
See section 6.6:
Signing and verifying using this key format is performed according to
the RSASSA-PKCS1-v1_5 scheme in [RFC3447] using the SHA-1 hash.
The resulting signature is encoded as follows: [snipped]
As indicated by that reference RFC3447 section 8.2 defines how to do this signature scheme; in particular it uses EMSA-PKCS1-v1_5
in section 9.2 which starts by applying the selected hash, in this case SHA-1, to the data to be signed.
Most other digital signature schemes, including DSA (called DSS in SSH) and ECDSA, also start by hashing the data, but you didn't ask about them.
RFC8332 says "SSH originally defined the public key algorithms "ssh-rsa" for server and client authentication using RSA with SHA-1".
That is correct, in section 1. Section 3 explains that the same keypairs used for ssh-rsa are reused for the new SHA-2 schemes, but:
Signing and verifying using these algorithms is performed according
to the RSASSA-PKCS1-v1_5 scheme in [RFC8017] using SHA-2 [SHS] as
For the algorithm "rsa-sha2-256", the hash used is SHA-256.
For the algorithm "rsa-sha2-512", the hash used is SHA-512.
(RFC8017 is PKCS1v2.2, which is an update to RFC3447 PKCS1v1.1. The algorithms and schemes are the same, but some new hashes are added. SHS is FIPS 180-4, the current version of the NIST standard defining SHA-1 and SHA-2 including SHA-256 and SHA-512.)
My understanding is that the server computes a hash of the public key using SHA-1 and when appropriate, sends both the public key part and its SHA-1 computed hash with to the client.
Am I correct?
No. The server sends the actual publickey, encoded as shown in RFC4253 6.6 and unchanged in RFC8332 3. As quoted above, the hash (SHA-1, SHA-256, or SHA-512) is applied to the data as part of the signature scheme.
This isn't in any way related to the fingerprint shown when we connect to an SSH server for the first time, is it? If not, how can I calculate it (without ssh-keygen)?
No. If you do want to calculate the fingerprint used by OpenSSH (not necessarily other implementations), it is either MD5 in hex with colons (for older versions) or SHA256 in base64 (for newer versions) of the key encoding sent on the wire. OpenSSH also stores the key blob in base64 in the id_xxx.pub, known_hosts, and authorized_keys files, so rather than actually contructing the encoding you can just base64-decode and hash the appropriate field from one of those files.
If you want to generate or verify a signature in SSH2 protocol, you need the to-be-signed data which as described in RFC4253 section 8 is the 'exchange hash' which is computed over data including the DH shared secret known only to the two endpoints of a particular connection, and so this computation can be and is done only by a program making a particular connection/session like the