The vast majority of "malware" on phones isn't software that exploits security bugs in the system software. Instead it's software that effectively asks the user nicely to give up their information, using mechanisms provided by the system software to do just that. This isn't something you can trivially prevent, as some software really does need access to your location, contacts, SMS, etc.
The response to true malware on Android isn't looking for and removing APKs from compromised devices after the fact, it's patching the vulnerabilities in system APIs.
The response to true malware on Android isn't looking for and removing APKs from compromised devices after the fact, it's patching the vulnerabilities in system APIs.