Regardless, KSP's workaround of using SOIs is simple and quite effective.
In any case, the bigger gameplay problem tends to be the vehicle physics simulation, where you have hundreds+ parts interacting and not in the most stable fashion especially above 2x time warp. That's the part that seemed amazing when KSP first came out, moreso than the orbital simulation (although the solar system exploration clinched the overall experience).
I don't understand how something that could easily be done on an 8 MHz computer in 1985 could strain a modern machine. Especially if you look up a decent algorithm and don't do the naive one.
Maybe there is some misunderstanding. Like, "n-body" to me doesn't imply a detailed simulation of inhomogenities in the celestial objects, like in real life they talk about mascons and such when landing on the moon. I'm assuming it's just that you calculate the forces of each body on every other body. And while you can do better than a simple N^2 calculation, if you have less than a dozen what does it matter?