I wondered about it but assumed it's a published design so they would be correct. But actually if your switching 20v it may well be inadequate. Bear with me a minute whilst I fire up LTSpice...
...ok this is taking longer than expected...
and leads to more questions...
So, the yellow trace is the base of Q1, yes? I don't see how you are getting a negative-going pulse there, since the output of the 555 should be positive-going.
The collector of Q1 is also negative going, which is correct. So either there's something wrong there, or you have channel 1 on the 'scope inverted, or you've build a part of the circuit which isn't present, or probed the wrong spot.
I used 1mH with 60R in series for the relay coil.
Ok, the simulation shows a reasonably clean signal so far. Also, the output of the totem-pole in the simulation is ok and synchronised with the input. It's showing total lag between input and output of a few hundred nS. Certainly nothing like the signals you are seeing.
Anyway, it confirms those transistors are up to the job and validates the design - well, as much as it can anyway.
I would re-check all the connections very carefully, look for solder bridges, or other shorts, open traces, check all the components are actually the values they say they are, and confirm that the transistors do actually work and that you have actually wired the circuit the way you think you have. As a low budget experimenter, I speak from experience....