When you're adding a contact on your phone, at the top the first option is to choose where to store the contact. Make sure you choose your Google account, not phone.
On my device, there doesn't seem to be an option to change the location. You could either re-enter them, or export them from the phone, put them on a pc & import them using a browser. You'll probably end up with multiple on the phone so you'll have to go back in & delete the ones stored there.