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.

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.