Instead of $f$, we consider the function $g(n)=f(n)/n$; wlog $f:\mathbb{N} \rightarrow \mathbb{N}$. The objective then follows from
$$\sum_{k=f(n)}^\infty \frac{a_k}{k\,g(k)} \leq c \sum_{k=n}^\infty a_{k\,g(k)}$$
for some constant $c>0$ and integer $n$, since the RHS converges.

1. If $g$ is bounded, that is $g(k)\leq m$ for some integer $m$, then
$$\sum_{k=1}^\infty a_{k\,g(k)} \geq \frac{1}{m}\sum_{k=1}^\infty m\,a_{km}\geq \frac{1}{m}\sum_{k=1}^\infty \sum_{l=0}^{m-1} a_{km+l} = \frac{1}{m} \sum_{k=m}^\infty a_k = \infty$$
since $a_k$ is decreasing. Thus $$\limsup_{n\rightarrow \infty} g(n) = \infty \, .$$

2. We consider the finite sum $\sum_{k=1}^N \frac{a_k}{k\,g(k)}$. If necessary, we may rearrage $\{g(1),g(2),...,g(N)\}$ in non-decreasing order and apply the rearrangement inequality $$\sum_{k=1}^{N} \frac{a_k}{k \, g(k)} \leq \sum_{k=1}^{N} \frac{a_k}{k\,g(\sigma(k))}$$
where $\sigma$ is a permutation of the $N$ points $\{1,...,N\}$ s.t. $g(\sigma(n))$ is non-decreasing on $[1,N]$. Thus for every $N$ we may assume $g$ to be non-decreasing.

We then decompose the sum in the following way
$$\sum_{k=f(n)}^{f(N+1)-1}\frac{a_k}{k\,g(k)} = \sum_{k=n}^N \sum_{m=f(k)}^{f(k+1)-1} \frac{a_m}{m\,g(m)} \leq \sum_{k=n}^N a_{f(k)} \, \frac{f(k+1)-f(k)}{f(k)\,g\left(f(k)\right)} \, . \tag{1}$$
Using $f(k)=k\,g(k)$, we can estimate the fraction on the RHS
$$\frac{f(k+1)-f(k)}{f(k)\,g\left(f(k)\right)} = \frac{g(k+1)-g(k)+\frac{g(k+1)}{k}}{g(k)\,g\left(k\,g(k)\right)} \, . \tag{2}$$

There are then two cases. The (possibly infinite) portion for which
1. $g$ stays finite as $N\rightarrow \infty$. This subcase is actually just those $k\in\{n,...,K-1\}$ s.t. $g(k)\leq 1+1/k$. In this case the RHS of (2) is clearly bounded by a constant.
2. $g$ increases to $\infty$ as $N\rightarrow \infty$. But then there exists $K$ s.t. $\forall k \in \{K,...,N\}$
$$k\,g(k) > k+1 \, .$$
It is then clear that the RHS of (2) is bounded by a constant since $$g(k)\leq g(k+1)\leq g(k\,g(k))$$ (in fact it even goes to zero).

It then follows that the RHS of (1) converges.