RSA key no longer accepted by OpenSSH 8.8+

Brief Description

Starting from OpenSSH 8.8, it no longer accepts RSA keys by default, causing kitchen creation failure. Manually SSH into the VM using the same key works but for some reason Test Kitchen fails to do so.

Version

Test Kitchen version 3.2.2
Vagrant 2.3.0
VirtualBox 6.1.38 r153438
Image bento/ubuntu-22.04
OpenSSH_8.9p1 Ubuntu-3, OpenSSL 3.0.2 15 Mar 2022

Environment

N/A

Scenario

Normal test kitchen run.

Steps to Reproduce

Specify ubuntu-22.04 in kitchen.yml:
```
platforms:
- name: ubuntu-22.04
```
Run kitchen create or kitchen converge

Observe the output

$ kitchen create
-----> Starting Test Kitchen (v3.2.2)
-----> Creating <default-ubuntu-2204>...
   Bringing machine 'default' up with 'virtualbox' provider...
   ==> default: Checking if box 'bento/ubuntu-22.04' version '202206.13.0' is up to date...
   ==> default: Machine not provisioned because `--no-provision` is specified.
   Waiting for SSH service on 127.0.0.1:2222, retrying in 3 seconds
   Waiting for SSH service on 127.0.0.1:2222, retrying in 3 seconds
   Waiting for SSH service on 127.0.0.1:2222, retrying in 3 seconds
   ...

Expected Result

Kitchen creation succeeds.

Actual Result

Kitchen creation stuck at "Waiting for SSH service on 127.0.0.1:2222, retrying in 3 seconds"

Additional context

Verbose logging shows authentication failure

D      [SSH] opening connection to vagrant@127.0.0.1<{:user_known_hosts_file=>"/dev/null", :port=>"2222", :compression=>false, :compression_level=>0, :keepalive=>true, :keepalive_interval=>60, :keepaliv
e_maxcount=>3, :timeout=>15, :keys_only=>true, :keys=>["/data/source/dotdotdot/cookbooks/server/.kitchen/kitchen-vagrant/default-ubuntu-2204/.vagrant/machines/default/virtualbox/private_key"], :auth_m
ethods=>["publickey"], :verify_host_key=>:never}>                                                    
D      [SSH] connection failed (#<Net::SSH::AuthenticationFailed: Authentication failed for user vagrant@127.0.0.1>)
       Waiting for SSH service on 127.0.0.1:2222, retrying in 3 seconds

Manually SSH into the VM works

$ ssh -i .kitchen/kitchen-vagrant/default-ubuntu-2204/.vagrant/machines/default/virtualbox/private_key -p 2222 vagrant@127.0.0.1

Auth log shows RSA key not accepted.

Sep  4 23:03:04 vagrant sshd[1441]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedAlgorithms [preauth]
Sep  4 23:03:04 vagrant sshd[1441]: Connection closed by authenticating user vagrant 10.0.2.2 port 43514 [preauth]

After adding the following lines to sshd_config, the issue is resolved

HostKeyAlgorithms=ssh-rsa,ssh-rsa-cert-v01@openssh.com
PubkeyAcceptedAlgorithms=+ssh-rsa,ssh-rsa-cert-v01@openssh.com

test-kitchen / kitchen-vagrant