Git SSH public key authentication failed with git on Azure DevOps

Add these lines to ~/.ssh/config before any wildcard entry:

Host ssh.dev.azure.com
  IdentityFile ~/.ssh/your_private_key
  IdentitiesOnly yes
  HostkeyAlgorithms +ssh-rsa
  PubkeyAcceptedKeyTypes=ssh-rsa

This link by @wcoder helped. Additionally, DevOps only allows deprecated ssh-rsa keys which new versions of OpenSSH now block

Finally, in even more absurdity, if you have a wildcard entry (Host *) you will need to exclude DevOps from using any keys in that entry because DevOps will blindly accept the first key that the client provides 🤦🏻‍♂️:

Host * !ssh.dev.azure.com
    ...