ssh tunnel not working in newer server installed (ssh-rsa no longer enabled)

Hello,

Fresh installs of Debian bookworm (12.5) do not seem to have ssh-rsa enabled by default.

When I try to connect to one of these hosts with Flyspeed + ssh key authentication, an error pops up:

SSH client connection failed. Message: Authentication failed 
publickey,password

The server logs an error like:

sshd[311757]: userauth_pubkey: signature algorithm ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]

I've upgraded to Flyspeed 4.8.6.0 (current latest), but this did not resolve it.

It works fine with password authentication (no ssh key) but most of the servers do not support password auth.

So. I generated a new ssh-ed25519 key pair. (Perhaps I should get with the times after all!)

However, when I try to add the ed25519 key to Flyspeed, I get an error:

"Error adding key to storage: Key is broken."

(Same ed25519 .ppk file works fine in PuTTY and Pageant, and I can login with this key successfully with PuTTY.)

It seems Flyspeed only supports ssh-rsa keys and not newer algorithms such as ed25519 (EdDSA) or ECDSA?

The workarounds:

1. Use password authentication (where this is enabled on the server)

or

2. Set the following in /etc/ssh/sshd_config:

PubkeyAcceptedAlgorithms +ssh-rsa

Then restart sshd:

systemctl restart sshd

Now it works with my old ssh-rsa ssh key as before.

Both of these are less than ideal, but work for now.

It's possible with opensshd server to add a match condition to allow it only for certain users or IP ranges, like so:

Match User bob,joe,fred
     PubkeyAcceptedAlgorithms +ssh-rsa

Or even:

Match User bob,joe,fred Address 192.168.10.0/27,2001:db8:209::/64
        PubkeyAcceptedAlgorithms +ssh-rsa

Note: No spaces between users/addresses

According to the man page, Match ..... PubkeyAcceptedAlgorithms is only supported on newer (OpenSSH_9.2) not earlier (OpenSSH_8.4 Debian 11 bullseye)

So rather than enable it globally on new hosts, it can enabled only for specific users/groups/networks (or even a special user just for Flyspeed to access the database)

(Debian: add to a .conf file like: /etc/ssh/sshd_config.d/sshd_ssh-rsa.conf and restart sshd.)