When OpenSSH 8.8, released Sep-2021, the "ssh-rsa" public key signature algorithm that depends on SHA-1 has been disabled by default:

This release disables RSA signatures using the SHA-1 hash algorithm by default. This change has been made as the SHA-1 hash algorithm is cryptographically broken, and it is possible to create chosen-prefix hash collisions for <USD$50K [1]

As a result a user using a version of Git that depends on OpenSSH 8.8, if they use an ssh-rsa keypair, will see failures of any hosting operation over SSH, for example:

git clone ssh://git@stash.example.com:7997/stash/stash.git
Cloning into 'stash'...
git@stash.example.com: Permission denied (publickey).
fatal: Could not read from remote repository.

And as OpenSSH 8.8+ is rolled out to the various operating systems the majority of Bitbucket Server users may be impacted by this problem.

There are a number of solutions or workarounds a user can use, and I'll list them in the "workarounds" section below. Here I propose implementing RFC 8332 such that the use of RSA based keys can continue with SHA-256 and SHA-512 used instead of SHA-1.

RFC 8332 permits, should both server and client support it, the user's existing ssh-rsa keys to be signed with either SHA-256 and SHA-512, this is known as rsa-sha2-256 and rsa-sha2-512. The OpenSSH 8.8 release notes actually call this out:

For most users, this change should be invisible and there is no need to replace ssh-rsa keys. 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.

However unfortunately Apache Mina SSHD does not currently support this, and as such Bitbucket Server does not support this. More specifically, it supports rsa-sha2-256 and rsa-sha2-512 however doesn’t implement the "server-sig-algs" extension required to notify the client of the additional signature algorithms.

Host Key Impact
The above discussion is referring to the SSH key pair that the client generates, however Bitbucket Server instances also have a key pair that is generated when it is first installed (or more specifically when SSH is first used). This key (the public key part) is provided to the client whenever the client makes an SSH connection, so is just as vulnerable to impact of deprecations as the clients key pair.

Prior to Bitbucket Server 6.6 Bitbucket Server supported neither rsa-sha2-256 nor rsa-sha2-512, only the original ssh-rsa SHA-1 algorithm was supported. As a result, even if users were to use an ECDSA or EC25519 based key, the host key validation would fail with OpenSSH 8.8+. Specifically requests will fail like so:

debug2: host key algorithms: ssh-rsa
..
debug1: kex: host key algorithm: (no match)
Unable to negotiate with 192.168.0.1 port 7999: no matching host key type found. Their offer: ssh-rsa

This was because the SSH server implementation Bitbucket Server uses, Apache Mina SSHD, did not support anything else. That changed in version 2.3.0: SSHD-895 - Add support for RSA + SHA-256/512 signatures

Bitbucket Server 6.6 was the first version to use Apache Mina SSHD 2.3.0, and since then is able to provide a host key via either rsa-sha2-512, rsa-sha2-256 or ssh-rsa. With modern versions of OpenSSH clients it will prefer the SHA-2 based signature and respond like so:

debug1: kex: host key algorithm: rsa-sha2-512

This is considered secure and is not deprecated by OpenSSH.

Workarounds

Move to a different key type
In addition to RSA, Bitbucket Server also supports ECDSA and ED25519 based keys. These keys are not impacted by the deprecation in OpenSSH 8.8. The current version of the Creating SSH keys documentation provides instruction for generating an ED25519 key.

Re-enable the disabled signature algorithm
The OpenSSH 8.8 release notes provide instruction to re-enable the disabled signing algorithm:

For example, the following stanza in ~/.ssh/config will enable
RSA/SHA1 for host and user authentication for a single destination host:

Host old-host
    HostkeyAlgorithms +ssh-rsa
    PubkeyAcceptedAlgorithms +ssh-rsa

We recommend enabling RSA/SHA1 only as a stopgap measure until legacy
implementations can be upgraded or reconfigured with another key type
(such as ECDSA or Ed25519).

Use HTTP/S
The HTTP protocol is not impacted; users already using HTTP for Git will be unaffected. This change can be as simple as changing the remote:

$ git remote set-url origin https://stash.example.com/scm/myproject/myrepo.git