The song is in A minor. He's soloing in both solos with A minor and there's also some classic minor pentatonic licks too. Sometimes he's got some chromatic stuff going on like around 1:58 wich seems to be a feature that keeps coming back in the song (solos, rhythm and bass). Like the bass around 20 sec.

Personally I would improvise over with A minor, sometimes adding some minor pentatonic licks that I can play fast and add some ascending or descending chromatic notes when it feels right (going to the next chord is often a good place to add chromatic walk down/up notes).