Why does the Neutrino cross-section increase with energy? There was a recent paper by IceCube on the measurement of Energy-dependent Neutrino cross-section. Here is the important Fig. 1 in the article:

x-axis is the Neutrino-Energy scale in logarithmic coordinates, and y is the cross-section $\sigma$ divided by energy (i.e. the constant dependence in the yellow low-every part means a linear increase of $\sigma$.
What confuses me is that the interaction increases with the Energy. My naive picture would be: The higher the Neutrino energy, the larger its velocity (because I would assume most of the Energy is in form of kinetic energy). Larger velocity means, the interaction time is lower, thus the cross section should be lower.
My naive and incorrect explanation for the Neutrino works for instance for the Cross sections of Neutrons.

Why does the Neutrino's Cross-Section $\sigma$ increase with the energy?

The article mentions some connections with the mediating bosons $W^{\pm}$ and $Z^0$, which explains the linear (up to 3TeV) behaviour and the ~$E^{0.3}$ behaviour for higher energies. However they don't detail this connection.
 A: Look at the review of Formaggio & Zeller, 2012, and in particular their eqn (14) for quasi-elastic neutrino scattering, 
$$
\sigma \propto G_F^2 s ~,
$$
where $G_F\propto 1/M_W^2 ~.$
The cross-sections are always complicated, but when you are just exchanging a W (or Z) at very high energy (their Fig.2), with momentum transfer below the $M_W$ scale, the only player is the denominator in the W propagator, so Fermi's "prescient" $G_F$ in the amplitude; and so its square in the rate/cross section. From dimensional analysis, you then need a power of s, the c.m. energy square, to match the dimensions of energy, in natural $c=1=\hbar$ units. $\sigma$ has dimensions of inverse energy squared, so the power of s on the right hand side must be 1, as above. 
In the lab/detector frame, for a target of mass m and negligible neutrino mass, 
$s=(E_\nu +m)^2-p_{\nu}^2 \sim 2mE_\nu $, so the above cross section indeed goes linear in the neutrino energy.
Now, in the paradigm of the review, (14), the target is an electron, but, instead, you are interested in the quarks inside the nucleons of matter, and the events are inelastic as the nucleons disintegrate at slightly higher q, and the quark/parton distributions of quarks in nucleons further shape the answer.  But, ultimately,  nothing will efface the above brutal, primitive dimensional fact...
Almost nothing. Unitarity QFT constraints cannot allow this indefinite rise of the cross section with energy. And, indeed, at very high energies, (don't let me estimate them... above a TeV, the scale of SSB) something has to give. Indeed, it does: Higgs exchange effects come to the rescue and limit the rise of the cross section with energy. (This, estimated in 1973 by  C.H Llewellyn-Smith      provided a major salutary boost to the SM picture.)
Still, the rise with E as a power of about 1/3 is an empirical  confluence of the struck relevant nucleon parton distribution effects averaged over momentum transfer, Ghandi et al 1996. I know of no easy argument to intuit it.
A: Cosmas has already given a nice answer to your question, but I'd like to make a comment on your "naive picture".
You are apparently aware that it's not how things really work, but the biggest flaw with your picture in this case is that there isn't even a difference in "interaction time". In all practical situations neutrinos move at the speed of light, no matter what their kinetic energy is. Due to their tiny mass, they can be considered to always travel at the speed of light. And as there is no difference in the "interaction time", there would also not be a difference in cross section.
A better way to imagine neutrino processes is to remember that the weak force (which governs neutrino interactions) is mediated by W and Z bosons. These are quite massive (80 and 91 GeV, respectively) and the energy to create them has to come from somewhere. Since the neutrinos in your plot only have a few GeV kinetic energy, the missing energy has to be "borrowed" from the vacuum. This is possible due to the Heisenberg uncertainty principle, which allows a violation of energy conservation, as long as it it is fixed again on a very short timescale. This is, a W or Z boson created from missing energy can only exist for an extremely short timespan, before it has to disappear again and restore energy conservation. However, the less energy they have to borrow, the longer these virtual bosons can exist. The longer these virtual bosons exist, the higher the probability that they mediate an interaction.
Consequently, the more energy there is available in the center of mass frame, the higher the probability for an interaction to occur (i.e. the cross section increases).
Of course, this is also just a rough illustration, but in my opinion it is a somehow more adequate description of neutrino interactions. For more detailed and correct explanations, the references provided by Cosmas are a very good start.
