Learn German: Die Arbeit war zu langweilig, weshalb ich einen Neustart wage. - The work was too boring, which is why I am daring a fresh start.

Because weshalb acts as a subordinating conjunction here. Instead of pointing to a specific noun, it refers to the entire previous situation (Die Arbeit war zu langweilig). Like other subordinating conjunctions, it kicks the conjugated verb (wage) to the end of its clause.

Could I use deshalb instead of weshalb in this sentence?

You could, but it would change the word order. weshalb means 'which is why' and creates a subordinate clause (verb at the end). deshalb means 'therefore' or 'that is why' and acts as an adverb starting a main clause. If you used deshalb, the verb would come right after it: ..., deshalb wage ich einen Neustart. You could, however, swap weshalb for weswegen, which works exactly the same way.

Is einen Neustart wagen a common phrase?

Yes, einen Neustart wagen (literally 'to dare a fresh start') is a fixed and very natural-sounding German expression. You will often hear it when someone takes a risk to start over, such as changing careers, moving to a new city, or completely changing their lifestyle.

Why do the two halves of this sentence use different tenses?