ssh-rsa keys (SHA-1 with old clients) no longer accepted in Gitlab 16.0 docker image

Gitlab 16.0 Community Edition docker image comes with a new baseline image of Ubuntu 22.04. This image comes with OpenSSH 8.9, a release that does not accept ssh-rsa keys by default. See release notes for OpenSSH 8.8.

This caught us by surprise since there is not mention about that in changelogs, and also according to documentation RSA keys are still being supported by Gitlab itself.

But when trying to ssh -Tvvv git@gitlab.our.host the following message appears in the container's logs:

==> /var/log/gitlab/sshd/current <==
2023-06-30_07:20:14.92265 userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]

I've managed to resolve this issue by adding the following crutch:

echo PubkeyAcceptedKeyTypes=+ssh-rsa >> /assets/sshd_config
service ssh reload

However I'd like to see this issue mentioned in the documentation and/or fixed on the level of gitlab-ce docker image.

EDIT: It's actually not as bad as it was described originally, see explanation in this comment.