The Wigner-crystal phase of two-dimensional electrons interacting via the Coulomb repulsion and subject to a strong Rashba spin-orbit coupling is investigated. For low enough electronic densities the spin-orbit band splitting can be larger than the zero-point energy of the lattice vibrations. Then the degeneracy of the lower subband results in a spontaneous symmetry breaking of the vibrational ground state. The $60^{circ}-$rotational symmetry of the triangular (spin-orbit coupling free) structure is lost, and the unit cell of the new lattice contains two electrons. Breaking the rotational symmetry also leads to a (slight) squeezing of the underlying triangular lattice.