The answer is "no" in general. There may be an elementary way of seeing this, but I will frame this in representation theoretic terms and will describe a general construction.
The question is equivalent to the following question: let $C_n$ be a cyclic group of order $n$, let $g$ be a generator, and let $\rho\colon C_n\to {\rm GL}_d(\mathbb{Z})$ be an integral representation of $C_n$, defined by $g\mapsto A$. Let $\sigma\in {\rm Aut}(C_n)$ be defined by $g\mapsto g^k$. Then is the integral representation $\rho\circ\sigma$ of $C_n$ isomorphic to $\rho$? Let me now explain a general construction of representations for which the answer is "no".
Set $d=\phi(n)$, the Euler phi function. For example if $n$ is prime, then we will have $d=n-1$. Fix a primitive $n$-th root of unity $\zeta_n$, and let $I$ be an ideal in $\mathbb{Z}[\zeta_n]$, the ring of integers of the $n$-th cyclotomic field $\mathbb{Q}(\zeta_n)$. Let $C_n$ act on $I$ by letting $g$ act by multiplication by $\zeta_n$. Since $I$ is an ideal, multiplication by $\zeta_n$ preserves it as a set, so this defines a representation $\rho_I\colon C_n\to {\rm GL}_d(\mathbb{Z})$. Moreover, it is not hard to see that if $I$ and $J$ are two such ideals, then $\rho_I$ is isomorphic to $\rho_J$ if and only if $I$ and $J$ represent the same class in the ideal class group of $\mathbb{Q}(\zeta_n)$. Finally, given $k$ coprime to $n$, there exists an element $\sigma$ of the Galois group of $\mathbb{Q}(\zeta_n)$ such that $\sigma\zeta_n = \zeta_n^k$. This $\sigma$ also defines an automorphism of $C_n$ via $g\mapsto g^{k}$. It is easy to see that $\rho_I\circ \sigma=\rho_{\sigma^{-1}I}$. Therefore, to produce an example of the type you desire, you can take a cyclotomic field in which the Galois group acts non-trivially on the class group and let $I$ be a representative of any class in the class group that is not preserved by the Galois group.
The smallest example that you can produce this way has $n=23$, $d=22$. Indeed, the cyclotomic field $\mathbb{Q}(\zeta_{23})$ is the first cyclotomic field with non-trivial class group, which has order $3$, and complex conjugation acts by $-1$ on it. So take any non-principal ideal $I$ in $\mathbb{Z}[\zeta_{23}]$, write down a $\mathbb{Z}$-basis for it, and write out the matrix $A$ of multiplication by $\zeta_{23}$ on this basis. Then $A$ will not be conjugate to $A^{-1}=A^{22}$ in ${\rm GL}_{22}(\mathbb{Z})$.