Why can't I ssh into a Vagrant Ubuntu 20.04 VM (focal) but I can to 18.04 and 16.04 VMs on the same host?

I’m running Vagrant 2.2.9 using Virtualbox 6.1.12. My host OS is Ubuntu 20.04

I need to run VMs with different versions of Ubuntu: 16.04 (xenial), 18.04 (bionic) and 20.04 (focal). Xenial and Bionic VMs are created fine and I can SSH into them, but I can’t SSH into Focal ones.

Simple .Vagrantfile:

 -*- mode: ruby -*-                                                                                                                                                                     
# vi: set ft=ruby :                                                                                                                                                                      
                                                                                                                                                                                         

VAGRANTFILE_API_VERSION = "2"                                                                                                                                                            
                                                                                                                                                                                         
Vagrant.configure(VAGRANTFILE_API_VERSION) do |config|                                                                                                                                   
  config.vm.box = "ubuntu/focal64"
                                                                                                                                                                                         
end

When I try to bring the focal VM up with vagrant up the process gets stuck on the default: SSH auth method: private key and eventually times out:

vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Importing base box 'ubuntu/focal64'...
==> default: Matching MAC address for NAT networking...
==> default: Checking if box 'ubuntu/focal64' version '20200720.0.0' is up to date...
==> default: Setting the name of the VM: testfocal_default_1595414135038_3222
==> default: Fixed port collision for 22 => 2222. Now on port 2205.
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
==> default: Forwarding ports...
    default: 22 (guest) => 2205 (host) (adapter 1)
==> default: Running 'pre-boot' VM customizations...
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2205
    default: SSH username: vagrant
    default: SSH auth method: private key
Timed out while waiting for the machine to boot. This means that
Vagrant was unable to communicate with the guest machine within
the configured ("config.vm.boot_timeout" value) time period.

If you look above, you should be able to see the error(s) that
Vagrant had when attempting to connect to the machine. These errors
are usually good hints as to what may be wrong.

If you're using a custom box, make sure that networking is properly
working and you're able to connect to the machine. It is a common
problem that networking isn't setup properly in these boxes.
Verify that authentication configurations are also setup properly,
as well.

If the box appears to be booting properly, you may want to increase
the timeout ("config.vm.boot_timeout") value.

vagrant ssh also times out after that

But doing the same process with xenial and bionic works fine, I can start the VMs and SSH into them just fine.

Looking at the output of vagrant ssh-config reveals a major difference between the two though:

For the working Xenial / Bionic VMs, the private key file used is one created at the project level:

vagrant ssh-config
Host default
  HostName 127.0.0.1
  User vagrant
  Port 2200
  UserKnownHostsFile /dev/null
  StrictHostKeyChecking no
  PasswordAuthentication no
  IdentityFile /home/adria/dev/testbionic/.vagrant/machines/default/virtualbox/private_key
  IdentitiesOnly yes
  LogLevel FATAL

But for the Focal VMs the private key file used is the one on the home folder:

vagrant ssh-config
Host default
  HostName 127.0.0.1
  User vagrant
  Port 2203
  UserKnownHostsFile /dev/null
  StrictHostKeyChecking no
  PasswordAuthentication no
  IdentityFile /home/adria/.vagrant.d/insecure_private_key
  IdentitiesOnly yes
  LogLevel FATAL

I’m creating all VMs in exactly the same way so I don’t know why in the focal case it’s picking a different private key. I’d be surprised if it was because the Host and Guest OS are the same but it’s the only thing I can think of.

Any ideas or pointers?