The claim is trivial for $d=1$. Now let $d\geq 2$. For any positive integer $d\geq 2$, $\{a^n\}_{n=1}^{\infty}$ is eventually periodic modulo $d$. Let $s_d$ be that period. It's known that $s_d<d$. We'll prove further: for every positive integer $d$, there exists infinitely many positive integers $n$ such that $d$ divides $ka^n + n$. We'll prove the claim by strong induction on $d$. Base case: $d=2$. For any positive integer $m$, choose $n=2m$ if $ak$ is even. Otherwise choose $n=2m+1$. Now let $d\geq 3$. Assume that the claim is true for $i=1,\dots,d-1$ and we'll prove that for $d$. By induction hypothesis, there exists a large enough positive integer $t$ for which $ka^t\equiv -t\pmod {s_d}$. We can choose $t$ such that $a^{t+ms_d}\equiv a^t\pmod {s_d}$ for any positive integer $m$. Choose an integer $u>t$ such that $u\equiv -ka^t\pmod {ds_d}$. Then $u\equiv t\pmod {s_d}$ so $ka^u\equiv ka^t\equiv -u\pmod d$ Since there are infinitely many choices of $u$, we are done.