Low-light shooting of moving subjects is best done with a 'fast' lens (low f number) and low magnification (if reasonable). In your case, you may have been shooting at f/6.3 since this is the best your lens is capable of at 300mm.
While shooting in low light, the best you can do is turn the aperture to the max, and the shutter speed to the minimum you can get away with.
Most zoom lenses have a maximum aperture that they achieve at all focal lengths, meaning that as you zoom in maintaining this maximum aperture, the f number increases. (f number scales like
aperture radius/focal length). For example, your lens' max f number varies from f/3.5 at 16mm to f/6.3 at 300mm.
A 'faster' lens (i.e. f/1.8) would have helped, but they are only economically accessible to most amateurs at short focal lengths (i.e. 50mm). For perspective, f/1.8 gives about 4 times as much exposure per second per ISO as f/3.5.
(3.5/1.8)^2=3.78 If you had zoomed in to 300mm and were consequently shooting at f/6.3, then f/1.8 would have given you
12.25x as much exposure for the same ISO and shutter speed! You could have reduced your ISO by a factor of 5x and still ended up with images twice as bright!
Reducing shutter speed:
Shooting with a shorter focal length (and getting physically closer to compensate) will reduce the effect of hand shaking, if that is an issue. If you were shooting at 300mm, then this may have been more problematic than the movement of the subjects themselves. Besides, getting closer is usually required to take advantage of a 'fast' lens since cheap ones have short focal lengths (i.e. 50mm) and zoom lenses have a lower f number at the short end.
Tracking your target in the viewfinder would help as well, allowing you to get away with a slightly slower shutter speed.
Lowering magnification has two benefits: it will increase depth of field, which is required for shooting at large apertures (i.e. f/1.8), and it will reduce the motion blur of the subjects in your frame, since they appear smaller. Of course, this requires changing the composition of your shot, but it's something to consider if you're having trouble getting good exposure otherwise.
A faster lens would definitely help you. There's a reason that f/1.8 and f/1.4 lenses are so popular (apart from the shallow depth of field...). However, to take advantage of one (assuming you don't have 1000+ USD to splurge on a professional f/2.8 telephoto or somesuch) you may need to get closer. Otherwise, you could accept the reduced magnification, and the greater depth of field and tolerance for subject movement that comes with it.
'Megazooms' like yours, covering wide angle to telephoto, will generally have poor image quality. There's always a sacrifice with lenses. In this case, you're sacrificing image sharpness, distortion and aperture for the convenience of a broad zoom range. If you know you're going to be shooting in low light in the future, then personally I would advise you to buy a relatively inexpensive f/1.8 prime lens (~100 USD for a crop sensor Nikon one). But that's up to you. You can get the most out of your lens by shooting at short focal lengths where the f number is lower-- this might be sufficient.
If money is no object, then a full frame camera, combined with an appropriately scaled focal length to match, will provide better low light performance than a crop sensor-ed camera.