`could not settle on host_key algorithm (SSHKit::Runner::ExecuteError)` with certificate based authentication

The stack trace points into Net::SSH's lib/net/ssh/transport/algorithms.rb and SSHKit's lib/sshkit/backends/netssh.rb; start by reproducing the certificate-based connection with the shown :ssh_options. Compare the client and server host-key preferences and determine whether SSHKit or its Net::SSH dependency can negotiate the advertised certificate algorithm. Done means a working certificate-authenticated connection or a documented, actionable incompatibility.

Hello,

Thanks for the nice software!

I am trying to use Capistrano in an environment with SSH certificate based authentication.
Passwordless authentication works flawlessly if a connection is performed directly using the OpenSSH client, however using Capistrano, the following happens:

Server host_key preferences: ssh-ed25519,ssh-ed25519-cert-v01@openssh.com                                                                                                                      
Client host_key preferences:                                                                                                                                                                   
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/algorithms.rb:381:in `negotiate_algorithms'                                                         
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/algorithms.rb:244:in `proceed!'                                                                     
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/algorithms.rb:184:in `accept_kexinit'                                                               
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:210:in `block in poll_message'                                                           
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:190:in `loop'                                                                            
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:190:in `poll_message'                                                                    
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:225:in `block in wait'                                                                   
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:223:in `loop'                                                                            
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:223:in `wait'                                                                            
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh/transport/session.rb:90:in `initialize'                                                                       
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh.rb:251:in `new'                                                                                               
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/net-ssh-6.1.0/lib/net/ssh.rb:251:in `start'
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/connection_pool.rb:63:in `call'
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/connection_pool.rb:63:in `with'
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/netssh.rb:177:in `with_ssh'    
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/netssh.rb:130:in `execute_command'
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/abstract.rb:148:in `block in create_command_and_execute'
        from <internal:kernel>:90:in `tap'                                                                                               
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/abstract.rb:148:in `create_command_and_execute'           
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/abstract.rb:80:in `execute'                               
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/capistrano-3.16.0/lib/capistrano/scm/tasks/git.rake:8:in `block (3 levels) in eval_rakefile'
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/abstract.rb:31:in `instance_exec'
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/backends/abstract.rb:31:in `run'                         
        from /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/runners/parallel.rb:12:in `block (2 levels) in execute'            
#<Thread:0x0000000002ed2298 /opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/runners/parallel.rb:10 run> terminated with exception (report_on_exception is true):
/opt/capistrano/.rvm/gems/ruby-3.0.3/gems/sshkit-1.21.2/lib/sshkit/runners/parallel.rb:15:in `rescue in block (2 levels) in execute': Exception while executing as user@host.example.com
: could not settle on host_key algorithm (SSHKit::Runner::ExecuteError) 

I tried specifying our global SSH config file (which includes the CertificateFile and IdentityFile parameters), and I additionally tried specifying the host_key manually:

set :ssh_options, {
     host_key: "ssh-ed25519-cert-v01@openssh.com",
     config: %w(/etc/ssh/ssh_config)
}

However the result does not change, neither if specified individually, nor if combined (as shown above).

The host_keys offered by the server, which Capistrano is showing, are correct - as confirmed using the OpenSSH client in verbose mode:

debug1: kex: algorithm: curve25519-sha256                                                                                                                                                      
debug1: kex: host key algorithm: ssh-ed25519-cert-v01@openssh.com                                                                                                                              
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none                                                                                            
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none                                                                                            
debug1: kex: curve25519-sha256 need=64 dh_need=64                                                                                                                                              
debug1: kex: curve25519-sha256 need=64 dh_need=64                                                                                                                                              
debug3: send packet: type 30                                                                                                                                                                   
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY                                                                                                                                                      
debug3: receive packet: type 31                                                                                                                                                                
debug1: Server host certificate: ssh-ed25519-cert-v01@openssh.com SHA256:XXXX, serial 0 ID "XXXX" CA ssh-ed25519 SHA256
:XXXX valid forever                                                                                                                                     
debug2: Server host certificate hostname: host.example.com                                                                                                                              
debug3: hostkeys_foreach: reading file "/home/user/.ssh/known_hosts"                                                                                                                          
debug3: hostkeys_foreach: reading file "/etc/ssh/ssh_known_hosts"                                                                                                                              
debug3: record_hostkey: found ca key type ED25519 in file /etc/ssh/ssh_known_hosts:1                                                                                                           
debug3: record_hostkey: found ca key type ED25519 in file /etc/ssh/ssh_known_hosts:2                                                                                                           
debug3: load_hostkeys: loaded 2 keys from host.example.com                                                                                                                               
debug1: Host 'host.example.com' is known and matches the ED25519-CERT host certificate.                                                                                                  
debug1: Found CA key in /etc/ssh/ssh_known_hosts:1

I could not find any references as to whether this the SSH library does not support certificate based authentication, hence am not sure if it is an issue with the software, or my setup. Given the convoluted output after Client host_key preferences: it sort of looks like the library not being able to handle ssh-ed25519-cert-v01@openssh.com, however I am not good enough with Ruby to debug it further.

Would appreciate any advice!