Mavericks SSH keys and Keychain
Are you sure you aren't using ssh-add from another source?  On my Mavs, ssh-add—which is /usr/bin/ssh-add—does have the -K flag.  It's in the manpage, shows in the usage message, and is accepted.

Check which ssh-add to see if you're pulling in ssh-add from elsewhere due to your PATH.