Phil Hartman was the biggest star on the show, and a big part of why the show worked. After his death, the show wasn't as good, and only lasted 1 more season, so I'd say he wasn't replacable. I can't think of anyone they could have brought in that would have had the same impact on the show that Hartman did.
Joe Rogan, despite being great in the role, was a supporting guy. Khandi Alexander had a supporting role. Phil Hartman was way more than just a supporting role.