Alina and Tina must sing more than $4$, but less than $7$, songs. Therefore, Alina sang $5$ or $6$ songs, and Tina sang $5$ or $6$ songs, with $4$ possible combinations.

However, since every song is a trio, if you add up all the numbers of songs a person sang for all four singers, it must be divisible by $3$. Thus, $7 + 4 + a + t$ must be divisible by $3$, and $a+t - 1$ must be divisible by $3$.

Since $10 \le a+t \le 12$ by the bounds of $5 \le a, t \le 6$, we have $9 \le a + t - 1 \le 11$. Because the middle number must be a multiple of $3$, we set $a + t - 1 = 9$, leading to $a + t = 10$ and $a = t = 5$.

So, the four girls sang $4, 5, 5$ and $7$ songs in trios. That means there were $\frac{4 + 5 + 5 + 7}{3} = 7$ songs sung, and the answer is $\boxed{A}$.