The "canonical" way to just build what was changed with make is to let the compiler generate header dependencies during the build and to include those (=> if you change only 1 header, just the affected translation units get rebuilt). Works like a charm (and never messes up incremental builds by not rebuilding on a header-only change).
If you did not have proper incremental builds before, I would blame the makefile specifically and not make itself.
Another way to mess up with make is to not allow anything in parallel, either by missing flags (-j) or by having a rule that does everything sequentially.
Ninja does have less overhead than make, but your build time should be dominated by how long compiler and linker take; such a big difference between the two indicates to me that your old make setup was broken in some way.