I have my main desktop (running Ubuntu Mate) and a laptop I use occasionally. I recently wiped the laptop and went from a testing distro to Ubuntu Mate on it. On the desktop, I have a bookmark in caja for the laptop via sftp. After reimaging, I purged the host key from ssh, and I can ssh to the laptop without issue. When I try to access sftp in caja, I get an error that "Host key verification failed." I have verified that ~/.ssh/known_hosts has no entry for the laptop. Where does caja store host keys if they're not in the user's known_hosts file?
As far as I know, caja doesn't store any keys, but uses whatever method is selected in the Connect to Server dialogue that you used to establish the connection the first time.
Have you tried deleting the bookmark and re-establishing it? File > Connect to Server, enter host name, choose port 22, Type: SSH, Folder, [User Name] [Password] click Add bookmark.
If you can SSH to the machine manually, this should also just work.