By using clean Android you give up all Google services, and that includes Gmail, YouTube, Earth&Maps, Google Play and many other things.
Additionally, most popular Android application depends or partially depends on Google Service. You either can't use the app or only can use few features if you don't have google services installed.
Can you give me more information on the way to use VPN for android devices, smartphones for example. I have not yet known how to stay private when browsing on mobile. There is no private browsers on mobile as far as I know (I might miscatch something).
Tor, Tor Browser, Brave Browser, Mozilla Firefox and various VPN application available either from Google Play Store or F-Droid.
It should be private enough for most people.