There are many many ways your being tracked by the apps and service you use
Unfortunately, a vpn is just the tip of the iceberg. It's a great first step but if you wanted to prevent your exact situation, I think only a phone running graphene OS would protect you in this instance since it isolates play services, among other privacy protecting features