Starting with some background information from Wikipedia, we have that under time reversal the position is unchanged while the momentum changes sign.
In quantum mechanics we can express the action of time reversal on these operators as $\Theta\,\mathbf{x}\,\Theta^\dagger = \mathbf{x}$ and $\Theta\,\mathbf{p}\,\Theta^\dagger = -\mathbf{p}$. It is worth mentioning here that the time reversal operator, $\Theta$, is anti-unitary, which allows it to be expressed as $\Theta = UK$ where $U$ is unitary and $K$ is the complex conjugation operator.
As for the creation/annihilation operators used in second quantization the sign changes under $\Theta$ would suggest a transformation of $a_r \rightarrow a_r$ and $a_k \rightarrow a_{-k}$. If you are worried about the fact that $k$ represents a crystal momentum and not a true momentum you can just take the position transformation, which is perhaps more trustworthy, and use $a_k = \sum_r \, a_r \,\mathrm{exp}[ -\mathrm{i} k\cdot r]$ to verify $a_k \rightarrow a_{-k}$ directly.
Using these transformations you should be able to verify that the tight-binding Hamiltonian is invariant under time reversal in position and momentum space for a lattice with or without a basis. Keep in mind that you would generally take the complex conjugate of the coefficients in $H$, however in your case $t$ and $\epsilon_k$ are both real. Its important to remember though, mostly to make sure $H$ stays hermitian.
As far as your comment about $\sigma_y$, this is only necessary if you include spin. Spin changes sign under time reversal so $\Theta\,\mathbf{S}\,\Theta^\dagger = -\mathbf{S}$. In this case, we can formally write $\Theta = \mathrm{exp}[-i \pi J_y]\,K$, which is probably the relation you are alluding to.
According to J.J. Sakurai's Modern Quantum Mechanics one possible convention for the time-reversed angular momentum states is $\Theta | j,m\rangle = (-1)^m |j,-m\rangle$. This suggests that with spin indices the creation/annihilation operators transform like $a_{r,m} \rightarrow (-1)^m\,a_{r,-m}$ and $a_{k,m} \rightarrow (-1)^m \, a_{-k,-m}$ under time reversal. From what I understand, most spin Hamiltonians will be invariant under this transformation. An example when this is not the case would be in the presence of an external magnetic field which couples to the spins through a $\mathbf{S}\cdot \mathrm{B}-$like term.
It is interesting how even in the absence of an external field the groundstate of spin Hamiltonians can still sponanteously break the time reversal symmetry present in $H$, but rather than discuss this myself I will direct you to this very well written answer.
Before you start your symmetry analysis, you have to define which system you consider. In this case, do you only consider the spin $1/2$-particle, or do you consider both the particle and the magnetic field along with its source?
If you consider both the particle and the magnetic field along with its source as your system, then yes, the system does have a time-reversal symmetry acting on all components.
If you only consider the particle as your system, then the external magnetic field must be kept invariant under time-reversal symmetry. In that case, the system is not time reversal invariant.
For spin-orbit coupling, the only reasonable choice is to choose the particle as your system. Then both momentum and spin change sign under time reversal.
Best Answer
I don't know the article you refer to, but I believe the Hamiltonian you discuss should get a $\pi$-phase shift after one turn around a (2D) lattice cell. So I guess it should read $H=F^{\dagger}\cdot H_{\pi}\cdot F$ with
$$H_{\pi}=t\left(\begin{array}{cccc} 0 & e^{\mathbf{i}\pi/4} & 0 & e^{-\mathbf{i}\pi/4}\\ e^{-\mathbf{i}\pi/4} & 0 & e^{\mathbf{i}\pi/4} & 0\\ 0 & e^{-\mathbf{i}\pi/4} & 0 & e^{\mathbf{i}\pi/4}\\ e^{\mathbf{i}\pi/4} & 0 & e^{-\mathbf{i}\pi/4} & 0 \end{array}\right)$$
and $F^{\dagger}=\left(\begin{array}{cccc} f_{1}^{\dagger} & f_{2}^{\dagger} & f_{3}^{\dagger} & f_{4}^{\dagger}\end{array}\right)$. Then, one has
$$H_{\pi}=\dfrac{t}{\sqrt{2}}\left[\left(1+\tau_{x}\right)\otimes\eta_{x}-\left(1-\tau_{x}\right)\otimes\eta_{y}\right]$$
where the $\eta$ and $\tau$ are the usual Pauli matrices.
Time reversal symmetry operator -- when it exists -- is defined as an anti-unitary operator which commutes with the Hamiltonian. Such an operator can be defined as $T=\mathscr{K}\tau_{z}\otimes\mathbf{i}\eta_{y}$ and thus $H$ is time reversal symmetric. $\mathscr{K}$ is the anti-unitary operator $\mathscr{K}\left[\mathbf{i}\right]=-\mathbf{i}$ and thus $\mathscr{K}\left[\eta_{y}\right]=-\eta_{y}$. One verifies that $\left[H_{\pi},T\right]=0$ as it must.
Please tell me if I started with the wrong Hamiltonian.
A few words about the definition (as follow from the comment below): The time-reversal operator is defined as I did, i.e. one applies it to the Hamiltonian $H_{\pi}$, (call it the Hamiltonian density if you wish, since in my way of writing $H=F^{\dagger}\cdot H_{\pi}\cdot F$, the dots should include summation(s) over phase-space-time [delete as appropriate]). You could prefer to define the action of an operator as transforming the operators (or the wave-function). But you should not use both definitions at the same time. It is clear that you can not do both, since otherwise you transform $H=F^{\dagger}\cdot H_{\pi}\cdot F \rightarrow F^{\dagger}\cdot U^{\dagger}\cdot \left(U \cdot H_{\pi} \cdot U^{\dagger}\right) \cdot U\cdot F = H$ trivially, whatever (anti-)unitary transformation $U$ you choose. It is clear that what your are looking for is something like $H=F^{\dagger}\cdot H_{\pi}\cdot F \rightarrow F^{\dagger}\cdot U^{\dagger}\cdot H_{\pi} \cdot U\cdot F \sim H$ and you see what I just said: apply the transformation to the Hamiltonian (density) or to the fields, but not both. In condensed matter we usually choose the convention I gave to you: we transform the Hamiltonian. One of the reasons is that the operators (especially the fermionic creation/annihilation ones) are seen as encoding the statistics of the fields, whereas the Hamiltonian encodes the dynamics, and it is simple imagination to change the dynamics.