I just ran into this same issue trying to connect from an Android 13 phone to an Ubuntu 22.04.2 server running OpenSSH 8.9p1.

The solution was indeed to switch the SSH Provider in the AndFTP connection advanced settings from Default to Secure (includes ED25519).