Let $(b_1, b_2, \dots, b_k)$ be a permutation of $\{a_1, a_2, \dots, a_k\}$ which is an arithmetic sequence in (mod $p$). Then, for some integers $c$ and $d$ we have $b_i \equiv c + i d \pmod p$ for every $i = 1, 2, \dots, k$.

It is easy to see that $k$ is the order of $a$ in (mod $p$). Then, we have $a^k \equiv 1 \pmod p$ and
$$b_1 + b_2 + \dots + b_k \equiv a + a^2 + \dots + a^k = \frac{a^k - 1}{a-1} \equiv 0 \pmod{p}.$$
On the other hand, we have
$$b_1 + b_2 + \dots + b_k \equiv \frac{k(2c + d(k+1))}{2} \pmod{p}$$
and hence, we get
$$2c + d(k + 1) \equiv 0 \pmod{p}.$$
Similarly, we have
$$b_1^2 + b_2^2 + \dots + b_k^2 \equiv a^2 + a^4 + \dots + a^{2k} = a^2 \frac{a^{2k} - 1}{a^2 - 1} \equiv 0 \pmod{p}.$$
since $1 < a < p-1$. Moreover,
$$\sum_{i=1}^{k} b_i^2 = \sum_{i=1}^{k} (c + i d)^2 = k c^2 + c d k(k+1) + d^2 \frac{k(k+1)(2k+1)}{6}$$
Therefore, we get
$$k c^2 + c d k(k+1) + d^2 \frac{k(k+1)(2k+1)}{6} \equiv 0 \pmod{p} \quad (2)$$
By (1), we can replace $c = -d(k+1)/2$ in (2) and get
$$\frac{d^2 k(k+1)^2}{4} - \frac{d^2 k(k+1)^2}{2} + \frac{d^2 k(k+1)(2k+1)}{6} \equiv 0 \pmod{p}$$
and hence,
$$\frac{d^2 k(k+1)}{2} \left( -\frac{k+1}{2} + \frac{2k+1}{3} \right) = \frac{d^2 k(k+1)(k-1)}{12} \equiv 0 \pmod{p}.$$
Clearly, $d \neq 0$ (mod $p$) and $2 < k \le p-1$. Therefore, we see that $k = p-1$.