Decomposing the Kraus operators in terms of the basis $\{E_i\}$ we write $A_i = \sum_j c_{ij} E_j$. Then
$$\mathcal E(\rho) = \sum_{jk}\Big(\underbrace{\sum_i c_{ij}\bar c_{ik}}_{\equiv \chi_{jk}}\Big) E_j \rho E_k^\dagger.$$
It follows that $\chi$, as a matrix, has the form $\chi = CC^\dagger$ with $C_{ij}\equiv c_{ji}$. For any $C$, the operator $CC^\dagger$ is positive semidefinite, hence the conclusion.
Equivalently, you may notice that the Choi representation of $\mathcal E$, which is defined as $J(\mathcal E)=(\mathcal E\otimes I)(d|+\rangle\!\langle +|)$ with $d$ the dimension of the underlying space and $|+\rangle=\frac{1}{\sqrt d}\sum_i |i,i\rangle$ the maximally entangled state, can be written in terms of the Kraus operators as
$$J(\mathcal E) = \sum_i \mathrm{vec}(A_i)\mathrm{vec}(A_i)^\dagger,$$
where $\mathrm{vec}(A_i)$ denotes the vectorisation of $A_i$. Decomposing $A_i$ as before, we get
$$J(\mathcal E) = \sum_{jk} \Big(\sum_i c_{ij} \bar c_{ik}\Big) \mathrm{vec}(E_j)\mathrm{vec}(E_k)^\dagger.$$
We can write this equivalently as $\chi_{jk}=\langle\!\langle E_j|J(\mathcal E)|E_k\rangle\!\rangle$, where I'm using the notation $|E_j\rangle\!\rangle\equiv\mathrm{vec}(E_j)$ and $\langle\!\langle E_j|\equiv\mathrm{vec}(E_j)^\dagger$.
In other words, $\chi$ is the Choi represented in the basis of (vectorisations of) the operators $\{E_j\}_j$. The Choi is positive semidefinite iff $\mathcal E$ is a channel, and thus so must be $\chi$.
