Thanks Andrew for the time you took investigating this.
So I understood right, this was a problem in the way Vagrant ruby library did ssh connection, as in presence of a ssh-rsa key it would always try to connect using a SHA-1 signature algorithm (the algo which was dropped by newer OpenSSH) instead of trying SHA-256 or SHA-512 (see https://github.com/hashicorp/vagrant/issues/11783#issuecomment-818951984) This means this was actually a bug in Vagrant, not in the boxes themselves. This is proved by your fact that the testing version of Vagrant can perfectly connect to the testing boxes. Not sure what to here, I am thinking of reassigning this bug report to the vagrant package, and maybe point the FAQ to this bug report.
