Before you go running off to a VPS or dedicated server, I would
certainly suggest looking into exactly what is causing the issue(s).
As
@Ulterios pointed out, I would definitely look into whether it
is just a shoddy host provider or what. Even with bursts of traffic,
any host, worth half a grain of salt, should be able to handle it.
Perhaps if you post who your current host is, you could get some
real feedback from others who may have used them in the past and
can give you some better insight by at least providing their experiences
with you which should help you make a more informed decision.
Also, when you say "traffic increased", could you elaborate a little.
If we're simply talking about a jump from 500 visitors to 5000 or so,
that definitely shouldn't cause any problems. If you're talking about
an astronomical increase, then there definitely could be other factors
at play.
On the other hand, if that is not the only problem you're experiencing
with your current hosting provider, then I would definitely suggest
shopping around for another host, however, I would not necessarily
go right for a VPS or even a dedicated server, not without knowing
exactly what the problem(s) is(are).