How do you translate "start"? I'm trying to ask, "Are you sure you want to start a new game?" My best guess is, 你確定要开始新遊戲？

I'm not sure whether I used "start" correctly.
Your guess is correct. You can use it as the following examples:

start a new game - 开始新游戏

start to do something - 开始做某事

a good start - 一个好的开始