Direct proof
We want to prove that a channel given in the form
$$\Phi(\rho) = \sum_a A_a \rho A_a^\dagger\tag1$$
can equivalently be represented as a unitary evolution in an enlarged space. I'll actually consider the more general case of an arbitrary (CP) map of the form (1) (that is, I won't assume the normalisation $\sum_a A_a^\dagger A_a=I$).
A direct way to do this is to define the operator $V$ with action
$$V|\psi\rangle\equiv \sum_a (A_a|\psi\rangle)\otimes |a\rangle.$$
If $\Phi$ is a channel, that is, $\sum_a A_a^\dagger A_a=I$, then $V$ is an isometry. The vectors $|a\rangle$ are here an (arbitrary) orthonormal basis in an auxiliary space. The auxiliary space needs to have dimension equal to the number of Kraus operators for this expression to work.
With this $V$, we can see that the map can be equivalently written as
$$\Phi(\rho) = \operatorname{Tr}_2[V\rho V^\dagger].\tag2$$
This is the so-called Stinespring representation of the map/channel. We can then also equivalently write (2) as
$$\Phi(\rho) = \operatorname{Tr}_2[U(\rho\otimes |u\rangle\!\langle u|)U^\dagger)],$$
for any pure state $|u\rangle$ living in the auxiliary space, defining $U$ as such that $U(|i\rangle\otimes|u\rangle)=V|i\rangle$.
This can always be done, and if $\Phi$ is a channel, then $V$ is an isometry, and $U$ is a unitary.
Proof with explicit componentwise expressions
From the Kraus representation, $\Phi(\rho)=\sum_a A^a \rho A^{a\dagger}$, making the indices explicit, we get
$$\Phi(\rho)_{ij}=\sum_{a,k,\ell}A^a_{ik}A^{a*}_{j\ell}\rho_{k\ell}.\tag1$$
On the other hand, unravelling the second expression we have for a generic $\sigma$ (let me here use numbers instead of latin letters for the indices, for better clarity, as well as Einstein's notation for repeated indices),
$$[U(\rho \otimes \sigma) U^\dagger]_{1234}=U_{1256}U^{*}_{3478}\rho_{57}\sigma_{68}.$$
Note that here the first two indices, ($1$ and $2$) correspond to the "output space" of the operator $\Phi(\rho)$, while the other two ($3$ and $4$) correspond to its "input space". Similarly, $2$ and $4$ live in the second Hilbert space, while $1$ and $3$ live in the first one.
Tracing with respect to the second Hilbert space amounts to introducing a $\delta_{24}$ factor, and we thus get
$$\left\{\mathrm{Tr}_B\left[ U(\rho \otimes \sigma) U^\dagger \right]\right\}_{13}
=U_{1256}U^{*}_{3478}\rho_{57}\sigma_{68} \color{red}{\delta_{24}}
=U_{1256}U^{*}_{3278}\rho_{57}\sigma_{68}.$$
If we take $\sigma$ to be a pure state, for example $\sigma=\lvert0\rangle\!\langle0\rvert$, so that $\sigma_{68}=\delta_{60}\delta_{80}$, then we have
$$\left\{\mathrm{Tr}_B\left[ U(\rho \otimes \lvert0\rangle\!\langle0\rvert) U^\dagger \right]\right\}_{13}
=U_{1250}U^*_{3270}\rho_{57}.$$
Going back to using the standard notation for the indices, and making explicit the sums, we have
$$\left\{\mathrm{Tr}_B\left[ U(\rho \otimes \lvert0\rangle\!\langle0\rvert) U^\dagger \right]\right\}_{ij}
=\sum_{a,k,\ell}U_{iak0}U^*_{ja\ell0}\rho_{k\ell}.\tag2$$
This expression is equivalent to (1), defining $A^a_{ik}\equiv U_{iak0}$ and $A_{j\ell}^{a*}\equiv U^*_{ja\ell0}$.
