I'm starting to think the reason is this one:

OpenSSH has supported RFC8332 RSA/SHA-256/512 signatures since release 7.2 and existing ssh-rsa keys will automatically use the stronger algorithm where possible.

So it seems OpenSSH v6.7p1 still wants to use SHA1 when confronted with an ssh-rsa key and the debug output (in the successful case)

debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: Server accepts key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit

was misleading and says nothing about which hashing algorithm was used in the client<>server communication.

All in all, having successfully wasted an entire night on this, I'm flabbergasted by how the OpenSSH developers didn't think that using ssh-rsa to mean "use RSA key", "use RSA + SHA1" or "use RSA + any SHA version" (depending on the situation) could be confusing. The RFC at least is very explicit.

I'm starting to think the reason is this one:

OpenSSH has supported RFC8332 RSA/SHA-256/512 signatures since release 7.2 and existing ssh-rsa keys will automatically use the stronger algorithm where possible.

So it seems OpenSSH v6.7p1 doesn't support SHA-256/512 yet and still wants to use SHA1 when confronted with an ssh-rsa key. In particular, the debug output (in the successful case)

debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: Server accepts key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit

was misleading and says nothing about which hashing algorithm was used in the client<>server communication.

Moreover, the RFC explains why my server didn't send server-sig-algs:

Servers that accept rsa-sha2-* signatures for client authentication
SHOULD implement the extension negotiation mechanism defined in
[RFC8308], including especially the "server-sig-algs" extension.

All in all, having successfully wasted an entire night on this, I'm flabbergasted by how it didn't occur to the OpenSSH developers that using ssh-rsa to mean "use RSA key", "use RSA + SHA1" or "use RSA + any SHA version" (depending on the situation) could be confusing. The RFC at least is very explicit.

I'm starting to think the reason is this one:

OpenSSH has supported RFC8332 RSA/SHA-256/512 signatures since release 7.2 and existing ssh-rsa keys will automatically use the stronger algorithm where possible.

So it seems OpenSSH v6.7p1 still wants to use SHA1 when confronted with an ssh-rsa key and the debug output (in the successful case)

debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: Server accepts key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit

was misleading and says nothing about which hashing algorithm was used in the client<>server communication.

I'm starting to think the reason is this one:

OpenSSH has supported RFC8332 RSA/SHA-256/512 signatures since release 7.2 and existing ssh-rsa keys will automatically use the stronger algorithm where possible.

So it seems OpenSSH v6.7p1 still wants to use SHA1 when confronted with an ssh-rsa key and the debug output (in the successful case)

debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit
debug1: Server accepts key: /home/user/.ssh/id_rsa RSA SHA256:<fingerprint> explicit

was misleading and says nothing about which hashing algorithm was used in the client<>server communication.

All in all, having successfully wasted an entire night on this, I'm flabbergasted by how the OpenSSH developers didn't think that using ssh-rsa to mean "use RSA key", "use RSA + SHA1" or "use RSA + any SHA version" (depending on the situation) could be confusing. The RFC at least is very explicit.