Restored Authenticator app lost all previously added accounts, now can't authenticate when needed. Locked out of other accounts as cannot authenticate.

Question

My phone died on me and won't start, I had to get a new phone. Luckily phone backed up itself before it died and I was able to do a full restore on my new phone. Authenticator automatically reinstalled on my phone with my user logged in, however ALL the stuff/accounts that I previously had on it are ALL gone! This was my main source for any authentications needed and now I can't get back into some stuff since I cannot turn on my old phone to authenticate anything and none of my accounts are on here for me to authenticate either. I don't know if this is supposed to work like this or if it's a bug. Is there anyway I can get all my accounts back on the app??? Or I to find my own way back into all the stuff I'm locked out of now.