In general it is not true. Let  $\{f_n\}_{n\geq 1}=\{1,z,\overline{z},z^2,\overline{z^2},\ldots\}$, then as the OP pointed out $a_n=o(n^{-k})$.
However, with a suitable permutation $\sigma$ of the basis  $\{f_n\}_{n\geq 1}$, we will have that coefficients in this new basis satisfy $\tilde{a}_n=a_{\sigma(n)}$. 
We can choose $\sigma$ so that for infinitely many $n$, $\sigma(n)\gg n$.Then it might happen for such $n$ that 
$$
\frac{\tilde{a}_n}{n^k}=\frac{a_{\sigma(n)}}{\sigma(n)^k}\left(\frac{\sigma(n)}{n}\right)^k\to \infty.
$$
Indeed, although $a_{\sigma(n)}/\sigma(n)^k$ is small, $(\sigma(n)/n)^k$ might be very large.
Providing a more explicit example from this sketch is now a simple exercise.