Detecting coplanarity by given pairwise distances
I think that if the input graph is 3-connected, and you assume some arbitrary origin and orientation, you can recreate the original points. Especially if you can find K_4 to seed the triangulation process.

Once we have the points, greedy strategies become available. They might not be optimal, but maybe they're enough for your purposes.

I've asked about recovering the embedding as a separate question.

Random Greedy

Until we have fewer than three not-disqualified points, arbitrarily pick three of them, yield the plane going through them, and mark all points on the plane as disqualified.

Take the remaining not-disqualified points (if any), pair them with some arbitrary disqualified points, and yield the plane going through them.

The planes we yielded covered all of the points. The number of planes we yielded is at most $\frac{n}{3}$, and each requires scanning through the remaining points, so this algorithm takes $O(n^2)$ time (faster than computing a determinant).

If the number of planes $k \ll n$, then we have reasonably good odds of hitting one of the large planes. I'm not sure what the expected running time is, but I would wild-guess it at $O(n \, k^3 \log k)$. (That's based on the coupon collector problem implying we need $\approx k \log k$ hits to collect $k$ planes, and that the odds of a hit are $\approx (1/k)^2$ so the expected time between hits is $\approx k^2$).

Prioritized Greedy

Another thing we can do, if we can solve for the points, is iterate over all triplets and count how many points are on that plane. Then we repeatedly yield the plane covering the most points, until no points are left.

If we don't account for disqualified points when choosing the next plane, then this takes $O(n^3 \log t)$ time where $t$ is the number of planes we return. If we do re-prioritize, then I think it can still be done in $O(n^3 \log t)$ (the number of disqualified points on other planes can only change by 2 so it might be possible to rebalance in some clever way).

This approach should do better, but again I don't think it's guaranteed to have $t=k$. We can probably arrange the points so that taking the plane covering most of them sends us down the wrong path.