How to uninstall Google/Samsung apps properly?
Install a custom ROM from the relevant XDA forum https://forum.xda-developers.com/samsung-a-series. Make sure you choose one that doesn't have GApps installed by default e.g. lite edition of this one. Then you can install microG (open source reimplementation) selectively as you require for apps that do need Play Services. 

I'm sure you could wrestle around with adb etc to get it working with your current setup but probably easier to start with a clean slate and make sure nothing is left behind if you are concerned about privacy.