Is there a map app that will work where there is no cell signal?
Also I don't like the idea that Google is tracking everywhere I go.
There are several alternatives, including caching maps when you are online for use offline. Do a search for "offline maps android".
You're using an Android phone, so Google is collecting information about you -- it's just the way things are. You can get an iPhone, if you'd rather have Apple collect information about you, or you can turn your phone off if you want to remain off the grid.