This is a thought. It might help. Dimension of a vector space is the number of vectors in a basis for that space. In your case, your vector space is $span(I,A^1,A^2,A^3,A^4,...)$. You already know any "vector" coming after $A^4$ i.e. $A^5$ and so on, can be written in terms of $(I,A^1,A^2,A^3,A^4)$. You also know know that there is a non-zero combination of this "vectors" that gives zero. So, they should be linearly dependent. This leaves the possible dimension to be less than or equal to 4.
$A^5=I$. This tells you that $A$ is invertible and hence diagonalizable. Also, the equation is satisfied by our matrix. Now any polynomial equation satisfied by the matrix should also be satisfied by the eigenvalues (where identity is replaced by one). In this situation, it is a 4 degree polynomial and has 4 roots. I numerically checked them. They are 2 distinct complex roots and their conjugates. Let them place at the diagonals of a diagonal matrix $D$. For some invertible matrix $P$, your $A$ should be $A=PDP^{-1}$. I observed that $D$ , $D^2$ and $D^3$ and $D^4$ are all same diagonal matrix with only the order of the diagonal entries changed. Now from the concept of minimial polynomials, it remains only to see if $n\leq 4$. Because, for any polynomial $p(.)$, if $p(A)=0$, it means the minimal polynomial of $A$ should divide it. So $n\leq 4$, otherwise you won't get a equation like this. In either case, the answer should be sort of min(n,4). ( I noticed it has been pointed out already).