Is the public part of that key in /home/user/.ssh/authorized_keys? Looking at the debug I'd say only the ssh-rsa key is in there, but I could be wrong!
Sorry, I looked and realized that authorized_keys didn't exist at all! Nonetheless, I copied the id_rsa.pub and id_ecdsa.pub inside it, but it didn't help.
$ rclone serve sftp b2: --user user --pass test --addr 127.0.0.1:2020
<5>NOTICE: Loaded 2 authorized keys from "/home/user/.ssh/authorized_keys"
<5>NOTICE: SFTP server listening on 127.0.0.1:2020
<3>ERROR : serve sftp 127.0.0.1:32920->127.0.0.1:2020: SSH login failed: ssh: no common algorithm for host key; client offered: [rsa-sha2-512-cert-v01@openssh.com rsa-sha2-256-cert-v01@openssh.com rsa-sha2-512 rsa-sha2-256 ssh-ed25519-cert-v01@openssh.com ecdsa-sha2-nistp256-cert-v01@openssh.com ecdsa-sha2-nistp384-cert-v01@openssh.com ecdsa-sha2-nistp521-cert-v01@openssh.com sk-ssh-ed25519-cert-v01@openssh.com sk-ecdsa-sha2-nistp256-cert-v01@openssh.com ssh-ed25519 ecdsa-sha2-nistp256 ecdsa-sha2-nistp384 ecdsa-sha2-nistp521 sk-ssh-ed25519@openssh.com sk-ecdsa-sha2-nistp256@openssh.com], server offered: [ssh-rsa]
Unless you have a different idea, I probably have to wait for a solution upstream.
Thinking a bit more about this, I think that's the wrong key, we need to change the private key of the server. Rclone normally generates an RSA key (cached here ~/.cache/rclone/serve-sftp/id_rsa) however you can set this with
--key stringArray SSH private host key file (Can be multi-valued, leave blank to auto generate)
So you could try creating a ecdsa key pair for the server