I feel that exactly the opposite should be the case; that is, dark matter halo should be inside the galaxy rather than outside.
Your feeling is entirely correct, and actually agrees with dark matter theories. Your only mistake is in thinking that the dark matter halo of those theories is only surrounding the galaxy; it's also inside the galaxy, and is usually most dense at the center of the galaxy.
A slight aside: The word "halo" is admittedly confusing here, because depictions of more modern times frequently show halos as isolated rings outside the head. The analogy would suggest that dark matter is just a ring outside the galaxy. Older (Western) art, however, showed halos as emanations of light originating behind the head, which is closer to the sense used in "dark matter halo".
To be a little more precise, dark matter halos are usually modeled by an NFW profile. This is defined by the density of dark matter $\rho$ as a function of the distance from the center of the galaxy $r$:
\begin{equation}
\rho(r) = \frac{\rho_0} {\frac{r}{R_s}\left( 1 + \frac{r}{R_s} \right)^2}~,
\end{equation}
where $R_s$ is some scale radius. As you can see, this density actually goes to infinity at $r=0$. That's okay; this is just a crude model, and the total amount of mass it describes is finite. But the point is that the density is greatest near the center of the galaxy, and gradually tapers off at larger radii.
You'll also see Einasto profiles, which have
\begin{equation}
\rho(r) = \rho_0\, \exp[-(r/R_s)^\alpha]~,
\end{equation}
where $\alpha$ is some other parameter. This one is finite at $r=0$ [in fact, $\rho(0) = \rho_0$]. And again, the density is always greatest at the center of the galaxy.
You'll sometimes even see the density profile approximated as uniform out to some radius $R_s$:
\begin{equation}
\rho(r) =
\begin{cases}
\rho_0 & r\leq R_s~, \\
0 & r > R_s~.
\end{cases}
\end{equation}
This is a particularly crude model, where you think of the galaxy as being basically embedded in a uniform glob of dark matter with constant density, but only out to some finite radius. The advantage of this is just that it's easier to make rough calculations with. This doesn't have greater density inside the orbits than outside, but at least it's not lower density.
Regardless of the particular model, the idea is always that there's extra matter inside the various orbits, which makes them behave exactly as you said.
Best Answer
It would probably be more proper to say that the galaxy rotates with the dark matter halo, since the mass of the halo is greater than the baryonic mass of the galaxy that we observe. Generally, dark matter halos have triaxial shapes, and shortest axis of the visible part of the galaxy will also be shortest axis of the dark matter halo.
EDIT: I should have been rather more careful. My answer is generally correct, I think, but there may be some more variation than I thought. A paper looking at spin of dark matter halos in the presence of baryons in the Millennium simulation sees a median misalignment between halo and baryonic (visible) galaxy of 30 degrees, and quite a total distribution. They further note that this misalignment seen in simulations will complicate mapping of dark matter halos with lensing measurements.