Simple fix:
Go to Play Console → Setup → App Signing, copy the SHA-1 and paste it into Firebase Console > Project Settings > Android App.
Download a new google-services.json after adding the key and add it to your app.
Go to Play Console → App Integrity → Link project, and link your Firebase project.
That’s it. Worked like a charm after publishing!