For anyone else that is having this issue in a new system adding a basic profile to /etc/apparmor/usr.sbin.sshd will allow you to use aa-genprof to profile sshd.

Example base profile:

# Last Modified: Wed May  6 12:41:39 2015
#include <tunables/global>

/usr/sbin/sshd {
  #include <abstractions/base>

  /usr/sbin/sshd mr,

This should also work for any other programs complaining about the rsyslogd dependency.