The recurrence relation can be rewritten as $x_{k+1} - 3 = x_k(x_k - 3)$. By repeating the process, we obtain
$$x_{k+1} - 3 = x_k(x_k - 3) = x_k x_{k-1}(x_{k-1} - 3) = \cdots = x_k x_{k-1} \cdots x_1(x_1 - 3).$$
Changing the index, this gives $x_k = 10x_2 \cdots x_{k-1} + 3$. We now prove the assertion by induction. The base cases $k=1$ and $k=2$ follow from $x_1 > 3$ and $x_2 = 13 > 9$. For the inductive step, we obtain
$$x_k > 10x_2 \cdots x_{k-1} > 10 \prod_{j=2}^{k-1} 3^{2^{j-1}} = 10 \times 3^{2+2^2+2^3+\cdots+2^{k-2}} = 10 \times 3^{2^{k-1}-2} > 3^{2^{k-1}}.$$
Thus, this holds for every positive integer $k$ by induction.

We prove by induction that $x_k \ge 3^{2^{k-1}} + 2$ for any $k$. The base case holds since $x_1 = 5$. Assuming $x_k \ge 3^{2^{k-1}} + 2$ for some $k$, we have
$$x_{k+1} = x_k(x_k - 3) + 3 \ge (3^{2^{k-1}} + 2)(3^{2^{k-1}} - 1) + 3 > (3^{2^{k-1}})^2 + 2 = 3^{2k} + 2.$$
The claim holds by induction. This obviously implies $x_k > 3^{2^{k-1}}$.