To increase Leadership, you need to create an army and lead it. You need to be in a Kingdom for that. Note that you can create an army with another member of your own Clan, so no need for influence. Having a party with food variety increases steward but not leadership. You just gain a few Leadership XP when recruiting, that's probably why you are at 22.