> Every time I use the Play store
Try F-Droid, a repository of FOSS apps with a focus on user confidentiality. They offer some security assurance by building and signing the apps from the orginal source, and offer nice functionality such as automatic updates (which you can disable, of course). Their store and related app is a fork of Aptoide. I often can find good solutions on F-Droid, but the repository is small.