But can we really know the 6th coordinate?
You are right -- given knowledge of five coordinates, there is a discrete choice (corresponding to a reflection) for the remaining coordinate. However, by convention we typically (but not always) use the word "degree of freedom" to mean a continuously varying quantity. This expresses the idea that you aren't free to choose the 6-th coordinate arbitrarily;arbitrarily as an initial condition; you have only finite number of choices for it. Once you have chosen your initial conditions however, the subsequent evolution from Newton's laws is completely fixed and there are only 5 functions of time you need to solve for.
If this is the effect of the constraint relation, then it doesn't really eliminate one redundant coordinate, but replaces the entire set, with one less coordinate.
I agree with your description that what is happening is "replacing the entire set, with one less coordinate." However, I also agree with the "eliminate one redundant coordinate" perspective. We started with $6$ coordinates and one constraint, and ended up with $5$ coordinates and no constraints; regardless of exactly how this was done, it seems fair to describe the net result as "eliminating" one of the 6 coordinates using the constraint.