I am adding this solution for anyone who comes to this thread:

First open this file on the host machine:

$ sudo vim ~/.vagrant.d/boxes/<yourbox>/include/_Vagrantfile

Verify that config.ssh.private_key_path is set to your private key file. If not update that

ssh to vagrant box with default pwd

$ vagrant ssh (default pwd = ‘vagrant’]

Once in the box:

vagrant@lucid64:~$ sudo visudo -f .ssh/authorized_keys

Add your public key to this file and save the file, and exit the box

vagrant@lucid64:~$ exit

Back to the local machine

$ vagrant halt
$ vagrant up

This worked for me

eth0 as NAT is a fundamental requirement of Vagrant in its current state. But you can override the default router configuration for eth1.

From the Vagrant docs:

Default Router

Depending on your setup, you may wish to manually override the default router configuration. This is required if you need access the Vagrant box from other networks over the public network. To do so, you can use a shell provisioner script:

config.vm.network "public_network", ip: "192.168.0.17"

# default router
config.vm.provision "shell",
  run: "always",
  inline: "route add default gw 192.168.0.1"

# default router ipv6
config.vm.provision "shell",
  run: "always",
  inline: "route -A inet6 add default gw fc00::1 eth1"

# delete default gw on eth0
config.vm.provision "shell",
  run: "always",
  inline: "eval `route -n | awk '{ if ($8 ==\"eth0\" && $2 != \"0.0.0.0\") print \"route del default gw \" $2; }'`"

Note the above is fairly complex and may be guest OS specific, but we document the rough idea of how to do it because it is a common question.