The two roots of the characteristic polynomial are $\{t,\bar t\}=\{\frac{1\pm\sqrt{13}}{2}\}$, so it is easy to see that $x_n=t^n+\bar{t}^n$. Firstly, $x_9-1=9$, so for $p=3$ it is satisfied, and also $x_n\equiv 1\forall n$, so we only need to worry about the factor $p$ inside $x_p-1$. Also, if $p=2$, $x_2-1=6$ so we don't need to worry about it. If $13$ is a quadratic residue $\pmod{p}$, then we can work $\pmod{p}$ to get $$x_p-1=t^p+\bar{t}^p-1\equiv t+\bar{t}-1=1-1=0\pmod{p}$$If $13$ is not a quadratic residue, then we can work in the quadratic extension of $\mathbb{F}_p$ $F=\mathbb{F}_p[\sqrt{13}]$. Here, $x\mapsto g(x)= x^p$ is an automorphism, meaning that $x^py^p=(xy)^p$ and $x^p+y^p=(x+y)^p$ (by binomial expansion). Therefore, if $t$ is a root of $x^2-x-3$ we have $(x^p)^2-(x^p)-3=(x^2-x-3)^p=0^p=0$, meaning that $x^p$ is also a root of $x^2-x-3$. In other words, $t$ and $\bar{t}$ can get permuted, but their sum stays the same. Therefore, $x_p=t^p+\bar{t}^p-1=t+\bar{t}-1=1-1=0+0\sqrt{13}$ in $F$, meaning that $p|t^p+\bar{t}^p-1=x_p-1$.

Note that $x_2=7\equiv 1 \pmod{(2\cdot 3)}$ and $x_3=7+3\cdot 1=10\equiv 1\pmod{(3\cdot 3)}$. Thus, let us consider $p>3$. Firstly observe that $x_n\equiv 1\pmod 3$ for all $n$, thus it is now sufficient to show that $p\mid x_p-1$ as $p\perp 3$. By generating functions, $$x_{n}=\left(\frac{1+\sqrt{13}}{2}\right)^n+\left(\frac{1-\sqrt{13}}{2}\right)^n \forall n.$$Now simply by binomial expansion, $$\left(\frac{1+\sqrt{13}}{2}+\frac{1-\sqrt{13}}{2}\right)^p-\left(\frac{1+\sqrt{13}}{2}\right)^p-\left(\frac{1-\sqrt{13}}{2}\right)^p\equiv 0\pmod p.$$