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 some large $n$, $\sigma(n)$ is small. Then it might happen for such $n$ that 
$$
\tilde{a}_n=a_{\sigma(n)}=o(\sigma(n)^{-k})\gg o(n^{-k}).
$$
Providing a more explicit example from this sketch is now a simple exercise.