This is a slight variation of the ideas behind the other answer.
Note that $\operatorname{Tr}(\Phi(\rho))=\operatorname{Tr}(\rho)$ for all states $\rho$ (read, all positive trace-1 operators) is equivalent to $\operatorname{Tr}(\Phi(X))=\operatorname{Tr}(X)$ holding for all operators $X$ (essentially because any operator can be written as a linear combination of positive operators, and the trace operation is linear).
Note that if $\Phi(X)=\sum_k A_k X A_k^\dagger$, then $\operatorname{Tr}(\Phi(X))=\operatorname{Tr}(X)$ is equivalent to
$$\operatorname{Tr}\left[X\left(\sum_k A_k^\dagger A_k\right) \right]=\operatorname{Tr}(X).$$
Because this must hold for any operator $X$, we can see what it amounts to for $X=\lvert i\rangle\!\langle j\rvert$.
Noting that $\operatorname{Tr}[|i\rangle\!\langle j| B]=\langle j|B| i\rangle$ and $\operatorname{Tr}[|i\rangle\!\langle j|]=\delta_{ij}$, this gives us
$$\langle i|\sum_k A_k^\dagger A_k |j\rangle=\delta_{ij}.$$
This is nothing but the componentwise version of $\sum_k A_k^\dagger A_k=I$.
Note that here I used a slightly different notational convention for the Kraus decomposition than the one used in the original post. The reason is simply that I am more used to this one, but you might simply replace each $A_k\to A_k^\dagger$ switch between the two conventions.