Attempt:
We work with $A'$, the matrix with entries $a_{ij}\mod 3$. Note that cubing $A'$ still gives $I$ as $I$ is unchanged by considering remainders $\mod 3$. For the rest of the proof, we will not differentiate between $A$ and $A'$. The minimal polynomial of $A$ divides $x^{3} - 1$ so each eigenvalue $\lambda$ of $A$ satisfies $\lambda^{3} = 1$. The trace of $A^3$ is clearly just $n$ as $A^3 = I$.
Next, note that for integers $a_1, ...., a_n$ we have that $(a_1 +... + a_n)^k = a_1^{k} + a_2^{k} ... + a_n^{k}\mod k$.
Now this is where I am stuck. I would like to say that this implies $\operatorname{tr}(A)^3 =\operatorname{tr}(A^3)$, but why is it that $\operatorname{tr}(A^3)$ is the sum of the cubed diagonal entries of $A$? I can only say that $\operatorname{tr}(A^3)$ is the sum of the cubed eigenvalues of $A$, but these eigenvalues need not be integers so the argument fails.
If I am able to prove this, then the result follows since I have $a^3 = a\mod 3$ for all $a$ in $\{0,1,2\}$.
Edit: I can confirm that my proof does work since $\operatorname{tr}(A)^p = \operatorname{tr}(A^p)\mod p$ for prime $p$ as said here https://rjlipton.wordpress.com/2009/08/07/fermats-little-theorem-for-matrices/
But I can't find the proof for this statement itself.