Navigation app lost after updating phone
The latest Google Maps app has the navigation function in-built. The navigation "app" was always integrated into Maps. The blue icon was just a separate entry point into that maps. 

If you select a destination, look at the bottom of the screen where it says navigate and you will recognize what comes up next.