My idea involves complex numbers, polynomials and some basic field theory. Let $l_1,\ldots,l_p\in\mathbb Q$ the lengths of the sides and write
$$\zeta=e^{\frac{2i\pi}{p}}.$$
If we assign to each vertex of the polygon a complex argument $z_1,\ldots,z_p$, we could choose $z_1=0$ and $z_1$ on the (positive) real line, so that
$$z_1=0,\:z_2=l_1,\:z_3=z_2+l_2\zeta,\:\ldots z_p=z_{p-1}+l_{p-1}\zeta^{p-2}$$
and the last relation is
$$z_1=z_p+l_p\zeta^{p-1}=0.$$
Compiling all these together, we obtain
$$l_1+l_2\zeta+\ldots+l_p\zeta^{p-1}=0.$$
So the polynomial
$$P(X)=l_1+l_2X+\ldots+l_pX^{p-1}\in\mathbb Q[X]$$
annulates $\zeta$.
By Eisentsein's criterion, you can prove that the polynomial
$$Q(X)=1+X+\ldots+X^{p-1}\in\mathbb Q[X]$$
is irreducible (this is the part where the primality of $p$ is essential). Indeed, remark that $Q(X)=\dfrac{X^p-1}{X-1}$ and that $Q(X)$ is irreducible if and only if $Q(X+1)$ is irreducible. But
$$Q(X+1)=\dfrac{(X+1)^p-1}{X}=X^{p-1}+\sum_{k=1}^{p-1}\binom{p}{k}X^{p-k-1}$$
so $p$ divides each coefficient of $Q(X)$ other than the dominating one, but $p^2$ does not divide its constant coefficient, since it is $p$.
Since $Q$ annulates $\zeta$ it is the minimal polynomial of $\zeta$, hence $Q(X)\mid P(X)$, but they are of same degree, so
$P(X)=\lambda Q(X)$ for some $\lambda\in\mathbb Q$. We can thus conclude that
$$\lambda=l_1=l_2=\ldots=l_p,$$
making the polygon regular.