Despite GitHub and 1Password recommending use of Ed25519 when generating SSH keys, Microsoft Azure Storage currently only supports RSA and ECDSA.
When debugging this, use:
sftp -vvv -i /absolute/path/to/private/key username@hostname