It seems interval is the way to go, from what I've read here and other forums so will be giving that a go.
Look, there's two fitness systems; aerobic and anaerobic. To be able to run at a level of endurance-speed you need a good fitness base; your aerobic engine. You train this by running at a low level, but by volume, obviously building the volume over time.
Speed work, like intervals can be added once you build that engine; speed work is like adding a turbo to the engine.
And you don't want to fit a turbo to a small engine.
So my suggestion is to increase your mileage, run all your runs at an easy pace, and build volume. After a few months, add speed work, like intervals, fartlek, strides, track work, and hill repeats. Keep speedwork to 10 to 20 percent of your overall volume; do more and you'll end up broken.
Rest is important too; that's when the adaptation to exercise takes place.
My fastest 5k was ran while I was doing 100% low heart rate training, while training for an ultra marathon; i.e. lots of slow miles. As I say, you don't need to train fast to be able to race/run fast. Speed isn't a problem for most folk; it's maintaining that speed over distance, and that's where your aerobic system comes into play.