Linode: Storing Videos & Streaming videos - Best methods for long videos

BACKGROUND:
I have hundreds of videos on my website, many of them are long. I use handbrake to reduce their size and to make them efficient re: audio, video, etc. I think I have got this relatively efficient. I store them as .mp4s. However, if anyone has suggestions on how to test the efficiency or make it more efficient, I'm open to ideas.

THE PROBLEM:
As my audience has grown I'm finding that I get Linode alerts at times and my audience complain about buffering - that my videos stop for 5 minutes and then they run for 5 minutes and then stop again.

I think I am exceeding my network out GPS limit.

WHAT I AM LOOKING FOR:
I'm looking for any advice on the most efficient methods of storing videos and trying to overcome this problem of buffering. It doesn't happen all the time. It mostly happens when I release a new video and people come to view it. Sometimes this buffering can continue for about 2 days. So it's not a problem that occurs all the time, it's happening some of the time. But it's increasing.

NB: I do NOT do live streaming. My videos are on my site and can be viewed at any time. But I'm creating new ones all the time and increasing the size of my video library.

I have some S3 storage, and I'm not sure if that will help.
Would other cloud storage possibly be of use?

Any suggestions are welcome.