SQL Agent not Running
Instead of having SQL Server monitor one of its subprocesses, why don't you have a script at the operating system level - WMI, PowerShell, what have you - periodically poll the services to make sure Agent is running? This seems a lot more foolproof than a startup procedure (which only runs when the SQL Server service starts, and potentially will finish before Agent starts, so it's not going to catch many scenarios - like when Agent suddenly fails or is forcibly shut down without touching the SQL Server service).

A job is absolutely not the way to do this. How can a job tell you that SQL Server Agent is not running? Catch-22. That's like your car driving itself to go get gas when it is out of gas.

Also, creating a watchdog for the Agent service seems way too reactive to me. Have you looked into why the service isn't starting or is getting shut down? The Windows event logs should have information about this.