Enter a new contact. You'll see, at the top of the screen, a pulldown that most likely says Device. That's the default (don't ask me why - it doesn't make sense, as you'll soon see). If you tap it, it drops down, and one of the choices is your Google account. Those are the only contacts that get backed up to Google. (You may also have a manufacturer account in there - ignore it for contacts - use your Google account.)
If the accounts had all been Google accounts, the phone would sync by itself and within a short time, they'd all be back on the phone. (Now you see why Device is a poor default choice.)
Bad news - you'll have to add all your contacts back by hand. But please, this time add them as Google contacts.