Automatically launching PuTTY with vagrant ssh

Try using this public key instead:

ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAQEAsD+KWzLA96mAM9hkwy/xWdRT6+aUJ72M2ZyrZMk/GZTGfZxPXKgNvhPB/2AF3tVikcp8XNw5iVN/Lfu6+9JCzeDl3E4r9Xcbx0zCeclOY8ofLCD1rsKRCC/E33aew/y4QMkGfZQeXj3mVsuQxuPrr5tCTziKUKz7QTNn/MLINa1YuqsO5aqO1ujCeT2RjwShXVcvjFzT9/fRXiaH0M1hygcuIYY3T8MOp6dGPoBHB6WOuVgv5X+BTsilRuL+mQTWnZZw93NF2ySgEZFHwPoMLBCCc+A1quZV+aoDBTaVsOdsSGeCWMAW5oytsG7M/ATUDmZOI7D+M9UWIXkdvImusQ==

and add this to the authorized_keys file.

There is an issue with the format of Putty-generated keys when used with SSH, it might easily be the cause of that error message you are seeing.

Update With regards to how to configure all this on Windows, have a look at this question on stackoverflow, maybe it will point you in the right direction.

Update 2 Try saving the public key as insecure_public_key.ppk (see this article)

Whenever I have seen ssh delays like the above, it was tied to DNS.

1) Check to see if "UseDNS No" is in your /etc/ssh/sshd_config file 2) if it is not (default is Yes and will be commented), backup your /etc/ssh/sshd_config file 3) Add UseDNS No 4) restart sshd (do not close your current ssh terminal if that is how you logged in) 5) open new putty, see if ssh is better

The reason not to close your old window: if for some reason you mess up syntax or the file, ssh server cannot start properly and you will not ssh in and need to go to the monitor, hard if you are remote. But if you still have your old window open, that won't close and you can copy your backup config back and restart sshd and regain access

Curious if this will work for you and if the different VM types was just a red herring